Pages: 1 ... 3 4 [5] 6 7 8   Go Down
Author Topic: Arbitrary precision (big number) library port for Arduino  (Read 11653 times)
0 Members and 1 Guest are viewing this topic.
Global Moderator
Netherlands
Offline Offline
Shannon Member
*****
Karma: 170
Posts: 12465
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
If anyone else is as stupid as me?? this might help if you are trying to figure out cos and tan!

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

BigNumber tane (const BigNumber x, BigNumber precision)
{
  BigNumber tan (((sine((x),precision) / cose((x),precision))));
  return tan;
}

From performance point of view one could check for the Taylor series of the TAN(x), especially if you need it as much as in "GEO-math"

update:
- http://www.haverford.edu/physics/MathAppendices/Taylor_Series.pdf - note that tan(x)  has 2 series !
- http://mathworld.wolfram.com/MaclaurinSeries.html - includes formulas

« Last Edit: August 09, 2013, 02:41:42 am by robtillaart » Logged

Rob Tillaart

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

UK
Offline Offline
Jr. Member
**
Karma: 0
Posts: 89
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Hello Rob,

Perhaps you over estimated how recently I had to consider maths of that level.... I have heard of Taylor series of course, but it is more years ago than I would like to recall!!  smiley-roll-sweat smiley-eek-blue

I will certainly look into implementing it when I get a bit of time.

Regards,

Graham
« Last Edit: August 11, 2013, 02:16:59 pm by ghlawrence2000 » Logged

UK
Offline Offline
Jr. Member
**
Karma: 0
Posts: 89
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Well, one could, and one did look into it, mmmm I think it is fine just the way it is (sin/cos).  smiley-roll

But thanks for the suggestion  smiley-grin

Regards,

Graham

Edit: I realised I am being a little slow on the uptake here..... But the implementation of SINE included in BigNumber library already IS Taylor series, thus figures that Sin(x)/Sin(x+90) is only slightly slower than 'native' Taylor Tan implementation? Not to mention I almost lost the plot trying to implement it... My 'native' Taylor series TAN implementation was massively slower than my original suggestion, so Rob, if you could post your solution, I would be interested to see it! Many thanks.
« Last Edit: August 16, 2013, 11:48:36 am by ghlawrence2000 » Logged

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: 452
Posts: 18694
View Profile
 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: 0
Posts: 57
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: 161
Posts: 10445
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: 452
Posts: 18694
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.
Logged

Global Moderator
Offline Offline
Brattain Member
*****
Karma: 452
Posts: 18694
View Profile
 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: 0
Posts: 57
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: 196
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 11 times.)
Logged

Offline Offline
Full Member
***
Karma: 2
Posts: 196
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: 196
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: 452
Posts: 18694
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.

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

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