Pages: 1 ... 3 4 [5] 6 7 8   Go Down
Author Topic: Arbitrary precision (big number) library port for Arduino  (Read 14388 times)
0 Members and 1 Guest are viewing this topic.
UK
Offline Offline
Jr. Member
**
Karma: 0
Posts: 89
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

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

Cheers, G
Logged

Offline Offline
Newbie
*
Karma: 0
Posts: 4
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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 
Logged

Global Moderator
Offline Offline
Brattain Member
*****
Karma: 474
Posts: 18696
Lua rocks!
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

In principle you probably can, however I expect you will run out of RAM first.
Logged

Offline Offline
Jr. Member
**
Karma: 1
Posts: 68
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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!
Logged

0
Offline Offline
Shannon Member
****
Karma: 200
Posts: 11671
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

[ I won't respond to messages, use the forum please ]

Global Moderator
Offline Offline
Brattain Member
*****
Karma: 474
Posts: 18696
Lua rocks!
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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:
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.
Logged

Global Moderator
Offline Offline
Brattain Member
*****
Karma: 474
Posts: 18696
Lua rocks!
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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:
-- 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.
Logged

Offline Offline
Jr. Member
**
Karma: 1
Posts: 68
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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:
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!
Logged

Offline Offline
Full Member
***
Karma: 2
Posts: 197
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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 "BigNumbler.cpp", etc., in order to avoid naming conflicts.

* Numbler4.zip (15.87 KB - downloaded 15 times.)
Logged

Offline Offline
Full Member
***
Karma: 2
Posts: 197
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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
Logged

Offline Offline
Full Member
***
Karma: 2
Posts: 197
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset


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 bigNumber(1L<<28).
Logged

Global Moderator
Offline Offline
Brattain Member
*****
Karma: 474
Posts: 18696
Lua rocks!
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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.
Logged

Global Moderator
Netherlands
Offline Offline
Shannon Member
*****
Karma: 211
Posts: 13478
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Rob Tillaart

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

Offline Offline
Newbie
*
Karma: 0
Posts: 3
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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...
Logged

Leeds, UK
Offline Offline
Edison Member
*
Karma: 78
Posts: 1719
Once the magic blue smoke is released, it won't go back in!
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

From the very first page of this thread:

Code:
BigNumber c = 0;
printBignum(c);

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

Or even just:

Code:
BigNumber c = 0;
c.printTo(Serial);
« Last Edit: November 30, 2013, 05:10:03 pm by Tom Carpenter » Logged

~Tom~

Pages: 1 ... 3 4 [5] 6 7 8   Go Up
Jump to: