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

This is really cool I was surprised at how fast it did it. Those are some pretty big numbers.
Logged

0
Offline Offline
Newbie
*
Karma: 0
Posts: 32
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Hi.

I am writing an emulation program for an old computer  - An Olivetti Programma 101, the first computer I ever encountered  when I was in high school and which really sparked my interest and probably changed my life. The 101 had quite a few unique and very clever features and used a system of 22 digit registers. I had started writing some code to do the same functions as the 101 supported in serial BCD representation covering add, subtract, multiply, divide (including remainder) and square root. I had the add and subtract routines working when I came across this post. With just a couple of extra things this library will do nicely. I need to know the length of the whole part of the number and the length of the fractional part.

The number.c and corresponding number.h seem best suited despite the more arcane calling process although using the BigNumber functionality certainly makes the process easy and logical. Good work all round.   If I have read the code correctly the information I want is the  n_len and n_scale of the target number.

Now I have to admit my C++ is pretty flaky and I don't tend to write libraries or use the macro capability of C much. I recognise the power of it but am not very familiar.  But I thought I had it by studying what was there and doing something similar. First I added a routine bc_size_whole_fraction to number.c as follows:

Code:
void
 bc_size_whole_fraction (num, size_whole, size_fraction)
      bc_num num;
      int *size_whole;
      int *size_fraction;
  {
   size_whole = num->n_len;
   size_fraction = num->n_scale;
  }

I thought this would take the number in question and return the size of the whole part and the faction part. Next I changed number.h as follows:
Code:
.
.
.
_PROTOTYPE(void bc_out_num, (bc_num num, int o_base, void (* out_char)(int),
     int leading_zero));
/* new line below*/
_PROTOTYPE(void bc_size_whole_fraction, (bc_num num, int *size_whole, int *size_fraction));

#endif

Finally I took a fragment of one of the test programs with just the multiply part so I could play around with it:
Code:
#include "number.h"  // this is the modified file as is number.c

static int DIGITS=1;

void print_bignum (bc_num x)
{
  char *s=bc_num2str(x);
  Serial.print (s);
  free(s);
}

void setup ()
{
  Serial.begin (9600);  // I am using a  Mega 1280 at 9600 baud.
  Serial.println ();
  Serial.println ();
  bc_init_numbers ();  // initialize library
 
  int sizew,sizef;

  // some big numbers
  bc_num a=NULL, b = NULL, c = NULL;

  Serial.println ("--- multiply ---");

  // test multiplication 
  bc_str2num(&a, "42.345",DIGITS);
  bc_str2num(&b, "18254546", DIGITS);
  bc_multiply(a,b,&c,DIGITS);

  // get results as string
 
  bc_size_whole_fraction(a,&sizew,&sizef); // read the sizes I am seeking for number a
  Serial.print("int ="); Serial.print(sizew); Serial.print("  "); Serial.print(sizef); Serial.print("  ");
  print_bignum (a); Serial.println();
  print_bignum (b); Serial.println();
  print_bignum (c); Serial.println();

  bc_free_num (&b);
  bc_free_num (&c);
 

}  // end of setup

void loop () { }

Now when complied i receive quite a series of errors:

sketch_jul06a.cpp.o: In function `print_bignum(bc_struct*)':
C:\DOCUME~1\Fred\LOCALS~1\Temp\build325333058827944339.tmp/sketch_jul06a.cpp:11: undefined reference to `bc_num2str(bc_struct*)'
sketch_jul06a.cpp.o: In function `setup':
C:\DOCUME~1\Fred\LOCALS~1\Temp\build325333058827944339.tmp/sketch_jul06a.cpp:21: undefined reference to `bc_init_numbers()'
C:\DOCUME~1\Fred\LOCALS~1\Temp\build325333058827944339.tmp/sketch_jul06a.cpp:31: undefined reference to `bc_str2num(bc_struct**, char const*, int)'
C:\DOCUME~1\Fred\LOCALS~1\Temp\build325333058827944339.tmp/sketch_jul06a.cpp:32: undefined reference to `bc_str2num(bc_struct**, char const*, int)'
C:\DOCUME~1\Fred\LOCALS~1\Temp\build325333058827944339.tmp/sketch_jul06a.cpp:33: undefined reference to `bc_multiply(bc_struct*, bc_struct*, bc_struct**, int)'
C:\DOCUME~1\Fred\LOCALS~1\Temp\build325333058827944339.tmp/sketch_jul06a.cpp:37: undefined reference to `bc_size_whole_fraction(bc_struct*, int*, int*)'
C:\DOCUME~1\Fred\LOCALS~1\Temp\build325333058827944339.tmp/sketch_jul06a.cpp:43: undefined reference to `bc_free_num(bc_struct**)'
C:\DOCUME~1\Fred\LOCALS~1\Temp\build325333058827944339.tmp/sketch_jul06a.cpp:44: undefined reference to `bc_free_num(bc_struct**)'


I am thinking this is an error which is readily fixed and caused by something I missed and can't see. Any suggestions?

Regards, Fred.
Logged

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

It's something to do with your setup. If I omit the line with your added function (bc_size_whole_fraction) and then compile I get your errors. But if I add:

Code:
#include "BigNumber.h"

instead of your include, it compiles OK. The IDE doesn't know where number.h is but it does know where BigNumber.h is (because it is in a directory of the same name inside the libraries folder).
Logged


0
Offline Offline
Newbie
*
Karma: 0
Posts: 32
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Thanks Nick. It certainly compiles now but returns rubbish. The numbers coming back regarding the length of the fractional and whole parts look random to me. More study needed. I'll make it work yet. Regards, Fred.
Logged

UK
Offline Offline
Full Member
***
Karma: 0
Posts: 101
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

This is awesome!

"New Arduino DUE(not delivered yet) looking for new home since this library appears capable of significantly higher precision than 'mere' DOUBLE floats..."

OOps!!

  smiley-roll smiley-cry smiley-roll-blue  smiley-mad

Second thoughts, I like the look of the speed advantages a DUE will offer over a MEGA!!  smiley-lol

Maybe some sticky or some reference to this library should be placed in the 'Reference' section to save other newbies making a similar mistake..

Excellent work Nick!
Logged

UK
Offline Offline
Full Member
***
Karma: 0
Posts: 101
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

OK, update since my last post....

I have done a fair bit of 'playing' with this library now, and also my DUE arrived  smiley-grin smiley-red. Sure enough this library can easily exceed the accuracy of DOUBLEs no problem, and on a DUE, it is almost 'rude' not to use it!! The speed is awesome!

However I have a question, once i have done all of my calculations and got the result I want, I have my BigNumber such as north = 449098.003294241285794.... and I would like the INT portion.... floor and ceil dont seem to work? Could you please tell me how to get int north or unsigned long north for example?

Just like to say thanks again Nick!

As a point of reference for other ''newbs' , the results achieved by this library are identical between a MEGA2560 and a DUE, the only difference is time taken to do the calculations...
Logged

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

If you know in advance how much precision you want you can use setScale. Otherwise:

Code:
#include "BigNumber.h"

void setup ()
{
  Serial.begin (115200);
  Serial.println ();
  BigNumber::begin ();  // initialize library
 
  BigNumber a, b = 2, c;
 
  BigNumber::setScale (2);
  a = BigNumber (1) / BigNumber (3);
  c = b.sqrt ();
  
  Serial.print ("1/3 = ");
  Serial.println (a);
  Serial.print ("sqrt(2) = ");
  Serial.println (c);

  BigNumber::setScale (20);
  a = BigNumber (1) / BigNumber (3);
  c = b.sqrt ();

  Serial.print ("1/3 = ");
  Serial.println (a);
  Serial.print ("sqrt(2) = ");
  Serial.println (c);

  long x = a;
  long y = b;

  Serial.print ("1/3 = ");
  Serial.println (x);
  Serial.print ("sqrt(2) = ");
  Serial.println (y);
}  // end of setup

void loop () { }

Output:

Code:
1/3 = 0.33
sqrt(2) = 1.41
1/3 = 0.33333333333333333333
sqrt(2) = 1.41421356237309504880
1/3 = 0
sqrt(2) = 2

By assigning to a long I have discarded the decimal places. You could convert that back to a BigNumber and subtract to get the decimal places alone.
Logged


UK
Offline Offline
Full Member
***
Karma: 0
Posts: 101
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

 smiley-roll-blue Sorry Nick! I did not pick up on that point earlier...

Yes, it works fine! Many thanks...

G
Logged

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

Can you repost with code tags please rather than "copy for forum"? Things like subscripts don't work properly.
Logged


UK
Offline Offline
Full Member
***
Karma: 0
Posts: 101
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Dont know how to do that, so I deleted the post, is that ok?

Sorry G.
Logged

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

Here:



The code was interesting, can you re-post it please?

Just copy the code directly from the sketch, (select all, copy), don't use the "Copy for Forum" "feature".
Logged


UK
Offline Offline
Full Member
***
Karma: 0
Posts: 101
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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;
}

That was how I implemented them anyway.

Also, I had a bit of a nightmare trying to implement LLtoNE in BigNumber format... If anyone else wants this, it is in the attachment.

Example output :-

Code:
Lat 53.121838, Lon -1.265120

Should give :- east 449174, north 358582
east 449174, north 358582
Lat 53.124981, Lon -1.298874

Should give :- east 446911, north 358909
east 446911, north 358909
Lat 53.144543, Lon -1.265869

Should give :- east 449098, north 361107
east 449098, north 361107

Over to you! Send Lat/Long pairs like this : 53.121838,-1.265120
             Send required Bignumber precision like this : #20

BigNumber precision changed to 8 digits

Lat 53.121838, Lon -1.265120
east 449174, north 358581
Time taken 582456 microseconds

BigNumber precision changed to 15 digits

Lat 53.121838, Lon -1.265120
east 449174, north 358582
Time taken 1652496 microseconds

BigNumber precision changed to 25 digits

Lat 53.121838, Lon -1.265120
east 449174, north 358582
Time taken 4398332 microseconds

That would be the bulk of the work required to implement Lat/Long to OSGB conversion for anyone that might be interested, WITHOUT needing to buy an Arduino DUE!!

However, just in case you need to justify to the missus, why you NEED a DUE, try this :-  smiley-eek smiley-wink

Code:
Lat 53.121838, Lon -1.265120

Should give :- east 449174, north 358582
east 449174, north 358582
Lat 53.124981, Lon -1.298874

Should give :- east 446911, north 358909
east 446911, north 358909
Lat 53.144543, Lon -1.265869

Should give :- east 449098, north 361107
east 449098, north 361107

Over to you! Send Lat/Long pairs like this : 53.121838,-1.265120
             Send required Bignumber precision like this : #20

BigNumber precision changed to 8 digits

Lat 53.121838, Lon -1.265120
east 449174, north 358581
Time taken 41125 microseconds

BigNumber precision changed to 15 digits

Lat 53.121838, Lon -1.265120
east 449174, north 358582
Time taken 103574 microseconds

BigNumber precision changed to 25 digits

Lat 53.121838, Lon -1.265120
east 449174, north 358582
Time taken 270292 microseconds


Ok so through experimentation 9 digits of precision is the minimum to achieve correct results, here are the performance figures for this function :-

Digits precisionMEGA2560DUE
90.689s0.048s
100.825s0.055s
151.652s0.104s
254.398s0.270s
smiley-eek-blue smiley-cry

I haven't understood how the "Arbitrary Precision" library works, is there any documentation about ?

Also, is there a real usage of this library ?

Yes!! This is one example! smiley-lol

I have also attached the natural 'DOUBLE' version of the same function. Depending on whether you have a DUE or not will reveal the weaknesses of single precision floats, particularly if you enter the same lat/long pairs used in the examples!

Cheers, G smiley-wink smiley-roll

* osgb36__osgridbignum.ino (7.91 KB - downloaded 13 times.)
* osgb36__osgrid.ino (5.53 KB - downloaded 11 times.)
« Last Edit: August 12, 2013, 01:46:23 pm by ghlawrence2000 » Logged

Global Moderator
Netherlands
Offline Offline
Shannon Member
*****
Karma: 224
Posts: 13915
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
Full Member
***
Karma: 0
Posts: 101
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
Full Member
***
Karma: 0
Posts: 101
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

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