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

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:

Code:
/*
* 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.
*/
Logged

Offline Offline
Edison Member
*
Karma: 11
Posts: 1489
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

OK, perfect, i will port it to my DSP =P

What do you think about my X-bits fixedpoint ?
do you think may be good to have a 64, or 128, or 256 bit fixedpoint math ?

in this case, it is called "fixedpoint", but you have to tune the position of the point
for example if you have 32bit you can choose 16 bit the integer part and 16 fit for the fractional part
or 24 bit for the integer part and 8 bit for the fractional part, or others combinations

the only important things is that you have to check that both the integer and the fractional parts have enough bits
in order to satisfy your constraints, for example ... the round/truncate error must be under the abs(error_max)

the arbitrary precision math is better but ... you have to pay
- speed
- memory consume



NASA used this "goal-tuned fixedpoint" working scheme for Apollo11
they did analysis and the choose the right amount of bits for both integer and fractional parts
Logged

Global Moderator
Offline Offline
Brattain Member
*****
Karma: 452
Posts: 18694
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

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: 25
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: 452
Posts: 18694
View Profile
 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: 25
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
Jr. Member
**
Karma: 0
Posts: 89
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
Jr. Member
**
Karma: 0
Posts: 89
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: 452
Posts: 18694
View Profile
 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
Jr. Member
**
Karma: 0
Posts: 89
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: 452
Posts: 18694
View Profile
 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
Jr. Member
**
Karma: 0
Posts: 89
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: 452
Posts: 18694
View Profile
 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
Jr. Member
**
Karma: 0
Posts: 89
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 7 times.)
* osgb36__osgrid.ino (5.53 KB - downloaded 5 times.)
« Last Edit: August 12, 2013, 01:46:23 pm by ghlawrence2000 » Logged

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