Go Down

Topic: Arbitrary precision (big number) library port for Arduino (Read 17 times) previous topic - next topic

ghlawrence2000

On the continuing quest for speed, the new and improved cos :-

Code: [Select]

BigNumber cose (const BigNumber x, BigNumber precision)
{
  const BigNumber pidiv2
    ("1.5707963267948966192313216916397514420985846996875529104874722961539082031431");
  return (sine((x+pidiv2) , precision ));
} // end of function cose


Cheers, G

malbahri

Hi,

I wonder if i could use this library to implement Elliptic Curve Cryptography. In other word I need to know to what extent this library can help achieving point addition and multiplication and binary field arithmetic.

BR//

Albahri 

Nick Gammon

In principle you probably can, however I expect you will run out of RAM first.
Please post technical questions on the forum, not by personal message. Thanks!

More info:
http://www.gammon.com.au/electronics

bilica

Great stuff! Thanks!

Any chance this might be adapted to receive hexadecimals as input also ? Every single char in the input char array could receive a number in the range of 0xFF.

Thanks!

MarkT

Excellent - any chance of a modexp() or isPrime() for RSA/DH/public key work?
[ I won't respond to messages, use the forum please ]

Nick Gammon


Great stuff! Thanks!

Any chance this might be adapted to receive hexadecimals as input also ? Every single char in the input char array could receive a number in the range of 0xFF.

Thanks!


Code: [Select]
BigNumber foo = 0xfe ;

But if you mean large numbers, I think a simple loop would achieve that. The number would have to be a string anyway, so you would pull in a character at a time, multiply the previous result by 16 and add the new one in, adjusting for the 'A' to 'F' range.
Please post technical questions on the forum, not by personal message. Thanks!

More info:
http://www.gammon.com.au/electronics

Nick Gammon


Excellent - any chance of a modexp() or isPrime() for RSA/DH/public key work?


Without making the core library larger you could implement those as simple functions, couldn't you?

Going back through some of my old posts I found a couple that might be relevant:

http://www.gammon.com.au/forum/?id=4988&reply=36#reply36

Code: [Select]

-- converts a hex string into a big number
function hex_to_bignum (h)
  local result = bc.number (0)
  local c, n
  assert (not string.match (h, "%X")) -- must be in hex
  for i = 1, #h do
    c = string.sub (h, i, i)  -- pull out digit
    n = tonumber (c, 16)      -- convert base-16 (hex) to decimal
    result = result * 16 + n  -- previous result 16 larger, then add in this digit
  end -- for
 
  return result
end -- function hex_to_bignum

-- See: http://en.wikipedia.org/wiki/Modular_exponentiation
-- (Right-to-left binary method)

function modular_pow (base, exponent, modulus)
  local old_digits = bc.digits (0)  -- working with integers
  local result = bc.number (1)

  base = bc.number (base)
  exponent = bc.number (exponent)
  modulus = bc.number (modulus)
 
  while not bc.iszero (exponent) do
    if not bc.iszero (bc.mod (exponent, 2)) then
      result = bc.mod (result * base, modulus)
    end -- if
    exponent = exponent / 2
    base = bc.mod (base * base, modulus)
  end -- while
 
  bc.digits (old_digits)  -- back to old number of digits
  return result
end -- function modular_pow


So there's the hex to bignumber and modexp.

That was for the big number library done for Lua inside MUSHclient, but the concept could be ported easily enough.
Please post technical questions on the forum, not by personal message. Thanks!

More info:
http://www.gammon.com.au/electronics

bilica



Great stuff! Thanks!

Any chance this might be adapted to receive hexadecimals as input also ? Every single char in the input char array could receive a number in the range of 0xFF.

Thanks!


Code: [Select]
BigNumber foo = 0xfe ;

But if you mean large numbers, I think a simple loop would achieve that. The number would have to be a string anyway, so you would pull in a character at a time, multiply the previous result by 16 and add the new one in, adjusting for the 'A' to 'F' range.


I mean large numbers - I will try this.

Thanks!

odometer

The BigNumber library has certain inefficiencies that seem to slow it down markedly when you run it on the Arduino platform.
The main one I would like to mention is occurrences of "divide by 10" or "modulo 10" in the code. (These also appear as "divide by BASE" or "modulo BASE", since BASE is defined as 10.) Perhaps this would not be so bad on a desktop computer with fast division or at least an optimizing compiler, but on the Arduino platform, division-- even integer division-- is painfully slow. I hand-optimized some of the relevant code.
I also noticed that the code for dividing BigNumbers seemed very peculiar indeed: the gymnastics that the code went through to get at the next digit of the quotient really did not make sense to me. As I still remember how to divide numbers using pen and paper, it was not hard to find a way to speed up the algorithm as well as economize on memory usage.

I would make it even more efficient, but I am really not that good at C++, and pointers drive me mad.

Please look at this version of the code and let me know what you find: problems, bugs (yes, there very well might still be bugs), etc.
Note: I have renamed the files "[font=Courier]BigNumbler.cpp[/font]", etc., in order to avoid naming conflicts.

odometer

And about any arbitrary-precision trig stuff (or indeed, any trig routines you want to make faster and/or more accurate): please see:
http://lolengine.net/blog/2011/12/21/better-function-approximations

odometer



But if you mean large numbers, I think a simple loop would achieve that. The number would have to be a string anyway, so you would pull in a character at a time, multiply the previous result by 16 and add the new one in, adjusting for the 'A' to 'F' range.


Faster perhaps to pull in two hex digits at once, and multiply by 256. Maybe a bit tricky if there is an odd number of hex digits.
I'd say "the heck with it" and probably pull in 7 hex digits at a time, and multiply by [font=Courier]bigNumber(1L<<28)[/font].

Nick Gammon


The BigNumber library has certain inefficiencies that seem to slow it down markedly when you run it on the Arduino platform.
The main one I would like to mention is occurrences of "divide by 10" or "modulo 10" in the code.


That wouldn't totally surprise me, as the original was probably written assuming people did in fact have access to floating-point co-processors.
Please post technical questions on the forum, not by personal message. Thanks!

More info:
http://www.gammon.com.au/electronics

robtillaart

maybe divmod10() can speed things up a bit  - http://forum.arduino.cc/index.php?topic=167414.0 -
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

104washington

Help! I'm an artist trying to use an Arduino Uno!

I'm new to this and having problems getting my Arduino Uno to calculate with large numbers.  I thought this library would solve the problem but I'm having trouble using it.  I've created a button that can measure the average duration between 10 button pushes.  It then uses the difference between the user's perceived duration of a second and the actual duration of a second to provide how that difference in time would add up over a lifetime.  My issue is in taking the difference, in the below example 183 milliseconds, and multiplying it up.

I have imported the library BigNumber, which puts the following at the top of my sketch:

#include <bcconfig.h>
#include <BigNumber.h>
#include <number.h>

I have inserted the following into my setup, as I either correctly or incorrectly understand that this is necessary:

BigNumber::begin ();

Then, I began testing it with the following code using the output from my program that produces the difference in milliseconds between their perceived second and an actual second:

  BigNumber a = 31557600;     //number of seconds in a year, which I would then multiply by average lifespan
  BigNumber b = milliSeconds;   //in this instance, milliSeconds = 183
  BigNumber c = 0;
  c = a*b;
  Serial.println(c);

The result I get in my monitor is:

-5627616

What am I doing wrong?  Please let me know if there is any other info I can provide that will help you help me.

Thanks in advance...

Tom Carpenter

#74
Nov 30, 2013, 11:06 pm Last Edit: Nov 30, 2013, 11:10 pm by Tom Carpenter Reason: 1
From the very first page of this thread:

Code: [Select]

BigNumber c = 0;
printBignum(c);

...
void printBignum (BigNumber n)
{
 char * s = n.toString ();
 Serial.println (s);
 free (s);
}


Or even just:

Code: [Select]
BigNumber c = 0;
c.printTo(Serial);
~Tom~

Go Up