Arbitrary precision (big number) library port for Arduino

Do you think a national bank of an EU state know they have 6.892.123.323.434,43Euro depth?

No, but they should have their debits and credits in balance, and no, they do not do their administration on an Arduino ;)

lock:
I haven’t understood how the “Arbitrary Precision” library works, is there any documentation about ?

Also, is there a real usage of this library ?

You may as well ask if there is a real usage for an Arduino that blinks a lot of LEDs. :wink:

The library was ported to the Arduino to show it could be done, and run in the small memory space available. In some cases, like GPS calculations, the extra precision (compared to 4-byte floats or 4-byte longs) might be required.

The documentation is largely by example, you can add, subtract, divide, multiply, take a square root, raise to a power, and do a “divMod”. Also comparisons are supported. See the .h file in the library for the exact details. You can operate to an arbitrary number of decimal places, and an arbitrary number of digits, subject to available memory.

The astronomers may like that even with arduino. For example calculation of the position of Sun, Moon, other celestial bodies, stars on the sky requires quite precise math. The single precision is not enough, you need at least double (we do not have). So you may use the library. Here is the library I used with an ARM when I toyed with large numbers, and documentation: http://speleotrove.com/decimal/decnumber.html http://speleotrove.com/decimal/decnumber.pdf That lib include arbitrary decimal floats (various formats), all math functions, afaik.

lock: do you think it is possible to port "Arbitrary precision (big number) library" to a C-only environment ? it may be useful in my DSP board, unfortunately it is supported only by a C toolchain, no C++ support at all. Let me know.

The original was written in C. In fact if you download my library the bulk of the work is done in number.c (and number.h) which are straight C.

The BigNumber.cpp and BigNumber.h files just provide "glue" routines to make the library easier to use. I didn't write the C part. It came from a port of the GNU bc library done for the Lua language:

/*
* this file is originally from GNU bc-1.06. it was trimmed down by lhf to fix
* a memory leak in bc_raisemod and to remove the free list, as in php bcmath.
*/

It could be OK, you might need to check the speed. The compiler supports long long (64 bits) but it generates a lot of code for it.

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

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:

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:

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

#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 tobc_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 tobc_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 tobc_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 tobc_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 tobc_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.

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:

#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).

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.

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

:roll_eyes: =( :roll_eyes: :0

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

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!

OK, update since my last post....

I have done a fair bit of 'playing' with this library now, and also my DUE arrived :D :blush:. 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...

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

#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:

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.

:roll_eyes: Sorry Nick! I did not pick up on that point earlier...

Yes, it works fine! Many thanks...

G

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

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

Sorry G.

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

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

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

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 :- :astonished: :wink:

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 precision MEGA2560 DUE
9 0.689s 0.048s
10 0.825s 0.055s
15 1.652s 0.104s
25 4.398s 0.270s

:fearful: =(

lock:
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! XD

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 :wink: :roll_eyes:

osgb36__osgridbignum.ino (7.91 KB)

osgb36__osgrid.ino (5.53 KB)

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

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

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!! :cold_sweat: :fearful:

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

Regards,

Graham

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

But thanks for the suggestion :D

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.