Arbitrary precision (big number) library port for Arduino

I love big numbers ... they are so ... big!

So in the spirit of getting your Arduino to handle nice, big, numbers I have ported (with pretty minimal effort on my part) the GNU "bc" library to an Arduino library. This can be downloaded from:

http://www.gammon.com.au/Arduino/BigNumber.zip

Just unzip into your "libraries" folder.

Example sketch:

#include "BigNumber.h"

static int DIGITS=0;

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

void setup ()
{
  Serial.begin (115200);
  Serial.println ();
  Serial.println ();
  bc_init_numbers ();  // initialize library

  char buf [10]; 

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

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

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

  // get results as string
  print_bignum (c);

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

  //factorials

  Serial.println ("--- factorials ---");
  bc_str2num(&b, "1", DIGITS);

  for (int i = 2; i <= 100; i++)
  {
    Serial.print (i);
    Serial.print ("! = ");
    bc_free_num (&a);
    sprintf (buf, "%i", i);
    bc_str2num(&a, buf, DIGITS);
    bc_multiply(a,b,&b,DIGITS);    
    print_bignum (b);
  }

  bc_free_num (&a);
  bc_free_num (&b);

  Serial.println ("--- power ---");
  
  // test powers  
  bc_str2num(&a, "2",DIGITS);

  for (int i = 1; i <= 300; i++)
  {
    Serial.print ("2 ^ ");
    Serial.print (i);
    Serial.print (" = ");
    bc_free_num (&b);
    sprintf (buf, "%i", i);
    bc_str2num(&b, buf, DIGITS);
    bc_raise(a,b,&c,DIGITS);    
    print_bignum (c);
    bc_free_num (&c);
  }  

}  // end of setup

void loop () { }

Output from above:

--- multiply ---
766690932
--- factorials ---
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
21! = 51090942171709440000
22! = 1124000727777607680000
23! = 25852016738884976640000
24! = 620448401733239439360000
25! = 15511210043330985984000000
26! = 403291461126605635584000000
27! = 10888869450418352160768000000
28! = 304888344611713860501504000000
29! = 8841761993739701954543616000000
30! = 265252859812191058636308480000000
31! = 8222838654177922817725562880000000
32! = 263130836933693530167218012160000000
33! = 8683317618811886495518194401280000000
34! = 295232799039604140847618609643520000000
35! = 10333147966386144929666651337523200000000
36! = 371993326789901217467999448150835200000000
37! = 13763753091226345046315979581580902400000000
38! = 523022617466601111760007224100074291200000000
39! = 20397882081197443358640281739902897356800000000
40! = 815915283247897734345611269596115894272000000000
41! = 33452526613163807108170062053440751665152000000000
42! = 1405006117752879898543142606244511569936384000000000
...
94! = 108736615665674308027365285256786601004186803580182872307497374434045199869417927630229109214583415458560865651202385340530688000000000000000000000
95! = 10329978488239059262599702099394727095397746340117372869212250571234293987594703124871765375385424468563282236864226607350415360000000000000000000000
96! = 991677934870949689209571401541893801158183648651267795444376054838492222809091499987689476037000748982075094738965754305639874560000000000000000000000
97! = 96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000
98! = 9426890448883247745626185743057242473809693764078951663494238777294707070023223798882976159207729119823605850588608460429412647567360000000000000000000000
99! = 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000
100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
--- power ---
2 ^ 1 = 2
2 ^ 2 = 4
2 ^ 3 = 8
2 ^ 4 = 16
2 ^ 5 = 32
2 ^ 6 = 64
2 ^ 7 = 128
2 ^ 8 = 256
2 ^ 9 = 512
2 ^ 10 = 1024
2 ^ 11 = 2048
2 ^ 12 = 4096
2 ^ 13 = 8192
2 ^ 14 = 16384
2 ^ 15 = 32768
2 ^ 16 = 65536
2 ^ 17 = 131072
2 ^ 18 = 262144
2 ^ 19 = 524288
2 ^ 20 = 1048576
2 ^ 21 = 2097152
2 ^ 22 = 4194304
2 ^ 23 = 8388608
2 ^ 24 = 16777216
2 ^ 25 = 33554432
2 ^ 26 = 67108864
2 ^ 27 = 134217728
2 ^ 28 = 268435456
2 ^ 29 = 536870912
2 ^ 30 = 1073741824
2 ^ 31 = 2147483648
2 ^ 32 = 4294967296
2 ^ 33 = 8589934592
2 ^ 34 = 17179869184
2 ^ 35 = 34359738368
2 ^ 36 = 68719476736
2 ^ 37 = 137438953472
2 ^ 38 = 274877906944
2 ^ 39 = 549755813888
2 ^ 40 = 1099511627776
2 ^ 41 = 2199023255552
2 ^ 42 = 4398046511104
2 ^ 43 = 8796093022208
2 ^ 44 = 17592186044416
2 ^ 45 = 35184372088832
2 ^ 46 = 70368744177664
2 ^ 47 = 140737488355328
2 ^ 48 = 281474976710656
2 ^ 49 = 562949953421312
2 ^ 50 = 1125899906842624
2 ^ 51 = 2251799813685248
2 ^ 52 = 4503599627370496
2 ^ 53 = 9007199254740992
2 ^ 54 = 18014398509481984
2 ^ 55 = 36028797018963968
2 ^ 56 = 72057594037927936
2 ^ 57 = 144115188075855872
2 ^ 58 = 288230376151711744
2 ^ 59 = 576460752303423488
2 ^ 60 = 1152921504606846976
2 ^ 61 = 2305843009213693952
2 ^ 62 = 4611686018427387904
2 ^ 63 = 9223372036854775808
2 ^ 64 = 18446744073709551616
2 ^ 65 = 36893488147419103232
2 ^ 66 = 73786976294838206464
2 ^ 67 = 147573952589676412928
2 ^ 68 = 295147905179352825856
2 ^ 69 = 590295810358705651712
2 ^ 70 = 1180591620717411303424
2 ^ 71 = 2361183241434822606848
2 ^ 72 = 4722366482869645213696
2 ^ 73 = 9444732965739290427392
2 ^ 74 = 18889465931478580854784
2 ^ 75 = 37778931862957161709568
2 ^ 76 = 75557863725914323419136
2 ^ 77 = 151115727451828646838272
2 ^ 78 = 302231454903657293676544
2 ^ 79 = 604462909807314587353088
2 ^ 80 = 1208925819614629174706176
2 ^ 81 = 2417851639229258349412352
2 ^ 82 = 4835703278458516698824704
2 ^ 83 = 9671406556917033397649408
2 ^ 84 = 19342813113834066795298816
2 ^ 85 = 38685626227668133590597632
2 ^ 86 = 77371252455336267181195264
2 ^ 87 = 154742504910672534362390528
2 ^ 88 = 309485009821345068724781056
2 ^ 89 = 618970019642690137449562112
2 ^ 90 = 1237940039285380274899124224
2 ^ 91 = 2475880078570760549798248448
2 ^ 92 = 4951760157141521099596496896
2 ^ 93 = 9903520314283042199192993792
2 ^ 94 = 19807040628566084398385987584
2 ^ 95 = 39614081257132168796771975168
2 ^ 96 = 79228162514264337593543950336
2 ^ 97 = 158456325028528675187087900672
2 ^ 98 = 316912650057057350374175801344
2 ^ 99 = 633825300114114700748351602688
2 ^ 100 = 1267650600228229401496703205376
2 ^ 101 = 2535301200456458802993406410752
2 ^ 102 = 5070602400912917605986812821504
2 ^ 103 = 10141204801825835211973625643008
2 ^ 104 = 20282409603651670423947251286016
2 ^ 105 = 40564819207303340847894502572032
2 ^ 106 = 81129638414606681695789005144064
2 ^ 107 = 162259276829213363391578010288128
2 ^ 108 = 324518553658426726783156020576256
2 ^ 109 = 649037107316853453566312041152512
2 ^ 110 = 1298074214633706907132624082305024
2 ^ 111 = 2596148429267413814265248164610048
2 ^ 112 = 5192296858534827628530496329220096
2 ^ 113 = 10384593717069655257060992658440192
2 ^ 114 = 20769187434139310514121985316880384
2 ^ 115 = 41538374868278621028243970633760768
...
2 ^ 288 = 497323236409786642155382248146820840100456150797347717440463976893159497012533375533056
2 ^ 289 = 994646472819573284310764496293641680200912301594695434880927953786318994025066751066112
2 ^ 290 = 1989292945639146568621528992587283360401824603189390869761855907572637988050133502132224
2 ^ 291 = 3978585891278293137243057985174566720803649206378781739523711815145275976100267004264448
2 ^ 292 = 7957171782556586274486115970349133441607298412757563479047423630290551952200534008528896
2 ^ 293 = 15914343565113172548972231940698266883214596825515126958094847260581103904401068017057792
2 ^ 294 = 31828687130226345097944463881396533766429193651030253916189694521162207808802136034115584
2 ^ 295 = 63657374260452690195888927762793067532858387302060507832379389042324415617604272068231168
2 ^ 296 = 127314748520905380391777855525586135065716774604121015664758778084648831235208544136462336
2 ^ 297 = 254629497041810760783555711051172270131433549208242031329517556169297662470417088272924672
2 ^ 298 = 509258994083621521567111422102344540262867098416484062659035112338595324940834176545849344
2 ^ 299 = 1018517988167243043134222844204689080525734196832968125318070224677190649881668353091698688
2 ^ 300 = 2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397376

Who would have thought your humble Arduino could calculate 100 factorial! Or 2 to the power 300! It runs pretty fast too. Takes a bit of memory though:

Binary sketch size: 12574 bytes (of a 32256 byte maximum)

I'm not really an expert on using the library, but hopefully the examples above will give you enough to go on with, to do things like add, subtract, divide etc.

(Output trimmed because of forum posting limits).

Just as another example, you can calculate "e" to around 100 digits like this:

#include "BigNumber.h"

static int DIGITS = 103;

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

void setup ()
{
  Serial.begin (115200);
  Serial.println ();
  Serial.println ();
  bc_init_numbers ();  // initialize library

  char buf [10]; 

  // some big numbers
  bc_num n= NULL, e = NULL, one = NULL;

  // the number: 1
  bc_str2num (&one, "1", DIGITS);

  e = bc_copy_num (one);
  n = bc_copy_num (one);

  for (int j = 1; j <= 200; j++)
  { 
    bc_num E = bc_copy_num (e);
    bc_num i = NULL;
    sprintf (buf, "%i", j);
    bc_str2num(&i, buf, DIGITS);
    bc_multiply (i, n, &n, DIGITS);  // n is i! (factorial of i)
    bc_free_num (&i);
    bc_num inverse = NULL;
    bc_divide (one, n, &inverse, DIGITS);
    bc_add (inverse, e, &e, DIGITS);
    bc_free_num (&inverse);
    if (bc_compare (e, E) == 0)  // sequence has converged
      break;
    bc_free_num (&E);
  }

  print_bignum (e);
} // end of setup

void loop () { }

Output:

2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274240

Time to execute: around 4 seconds.

(edit)

Theory:

E can be calculated as:

1 + (1/1!) + (1/2!) + (1/3!) ...

That's why the code above is calculating running factorials, and adding the inverse of the factorial to the running total. The code breaks out of the loop when, for the desired number of decimal places, the calculated value doesn't change. That is, at this level of precision, the new amount added does not change the result.

That is impressive....

Really.... !!! and 12K inside the chip...

Still impressive...

Well done Nick!

it was somewhere (low) on my todolist and now you did it,

thanks,

I just tried it out on a Mega

877! = 1011611483741808350979735614596014894238217322814495678061885986476300120788475589798361596687802128663578042330388633117314918769911893358399855960767087128402653443885249004974897395365479609012783486035483721056839305679987543322025849969875662030830862782926142893333372401656801048774838842075152998418255972797905783699836709546309855893192339084006473628589802797018620887820660848933680457891211257009195751003942681086243147771699300541509917023520768906796204790094872374055294488039306715002830688899997703266103221933805878232123922606100282667038975335043142164163282886560774853187972831209054672730754941302295267776051816732092387029190871291957841784343189241963815856213180566177167112195639046498955376116343921497000536730892516289134843911964047782503358856762108229999177212919928477847641247924465566305875742648991423035640465076829096936501640889769710663169426265396877392790851591894194592057595867010347648202135987859552881929151183698789144026592022450651849397915054771736000737211818458904512736028771559016796149604022595483819743035778947290107102852122610304080676169477575467029871046405065014560927549248111540931483826114271560342485211947257026936230866153767287913951996901524008773010016174894707271992213946054234643582296721076221917553548823648235881143398824484971152482893217762115260242215038066422004691931201792687326732904794242502893084554255994244841293557872138759903613572361115372118957926480182881795156632473733548929885690977865413771097341102912144355671697711537730972632264019256588811705253789509886640902406984090032313082820615025013367001560652771755174854201473950778204978987557794358451512535545900895512531104615368723488464504058808076406951191668900760904086410146183739769732997767263632442026777218726524601613206446515770406124734920046269981962123073162988129456830952669379413202410563973619772261016585559412160000284936236613564082779335945761084993654032138109517877957056794329153855895700267217477802393600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
878! = 888194882725307732160207869615301077141154809431127205338335896126191506052281567842961481891890268966621521166081219877002498679982642368675073533553502498737529723731248626367959913130891096713223900739154707087904910387029063036738696273550831263069497523409153460346700968654671320824308503341984332611228744116561278088456630981660053474222873715757683845901846855782349139506540225363771442028483483654073869381461673993721483743551985875445707146651235100167067805703297944420548560498511295772485344854197983467638628857881561087804804048156048181660220344167878820135362374400360321099040145801550002657602838463415245107373495090777115811629584994338985086653320154444230321755172537103552724507771082826082820230149963074366471249723629301860392954704433953037949076237131025939277592943697203550229015677680767216558902045814469425292328337455947110248440701217805962262756261018458350870367697683102851826569171235085235121475397340687430333794739287536868455347795711672323771369418089584208647271976606918162182233261428816747019352331838834793734385413915720714036304163651846982833676801311260052226778743647082784494388239841932937842799328330429980702016089691669650010700483007678788449853279538079702702794201557552984809163844635618017065256521104922843612015867163151103643904167897804671879980245195137198492664803422318520119515595173979472871490409344917540128238636762946970655743811737831195372716533059296720445059449600570216147523311938055960439636678565833291023465488356862744279750590730127793971127808907284976677212827189680470712313332031048370886716499991961736227370253133601043521988894128783263971551075743446720428006209300986260002309852293739222871834563633491085303146285294868073787868108349323517825572039657469284099510398041888600216395260040846416577517259800625044162744058237103577663097576443715124791716475168838160045172562121163876480250174015746709264680256960378232624428240217260156696846295865420997085476424834616945510501580800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
879! = 780723301915545496568822717391849646807075077489960813492397252694922333819955498133963142582971546421660317104985392271885196339704742642065389635993528696390288627159767542577436763642053274010923808749716987530268416230198546409293314024451180680238088323076645891644750151447456091004567174437604228365270066078457363439753378632879187003841905996151004100547723386232684893626248858094755097543036982131930931186304811440481184210582195584516776581906435653046852601213198893145662184678191428984014618126840027468054354766077892196180422758329166351679333682523565482898983527097916722246056288159562452336032895009342000449381302184793084798422405210023967891168268415756478452822796660114022844842330781804126798982301817542368128228507070156335285407185197444720357238012438171800625004197509841920651304780681394383355274898270918624831956608623777509908379376370451440828962753435224890415053206263447406755554301515639921671776874262464251263405575833744907372250712430559972595033718500744519400952067437481064558183036795929920630010699686335783692524778831918507637911359849973497910801908352597585907338515665785767570567262821059052363820609602447953037072142838977622359405724563749655047421032713972058675756103169089073647255019434708237000360482051227179534961947236409820102991763582170306582502635526525597475052362208217979185054208157927956654040069814182517772721761714630387206398810517553620732617832559121817271207256198901219993672991193551189226440640459367462809626164265682352221900769251782330900621344029503494499270075099729133756123418855291518009423803492934366143858452504435317255828237939200489030993395578489667256217457975566922542030360166196776904342581433838663981465584774189036859536067239055372168677822858915500723469639878820079590211433575904000171637671364749413819052027190414044765862769694025594691918781673408742679706682104503047426139902959841357443653945868172466476872423150971677736527894065705056438133777429628295103730889523200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
880! =     hang :-(

It's just gone past 2^2500, no sign of slowing down yet 8)

Spoke to soon, it only got to 3185

2 ^ 3185 = 60330397918169067189154859614195658578960897296929132962593558049265765414244113975717036406695955294778266745091693982817625978318696612820582862384038055854166537542575121279329133961851443691552744175104330258624537514699141306573923539562675206421184314042605709311651239977642668288061008842030557465198894017617518137167372250079891745439494701245953014651529419254590665425478664809001959792775079170013398861424297560604506897073366872439885664916900741398920596138670273011016060545453329652040655827952238820288172583118930690468240119894979642483984048201147481246325895740120174209451268526360208340284086755025608822644896082254040333252186566093203937853205213188254709026343772013543819332559182163519537693217193638171552942183758849465320654699359439479612108453048481459525654111482698136626063904655038833592038046021537949736085393139963116317798448755326775429413795753417152431231174220386227671901895312112340642796184959282876495429632
2 ^ 3186 =   hang :-(

It should be able to get a lot further - 877! is around 2^7334 - maybe there's some memory fragmentation issues going on.

It wouldn't surprise me a bit about the fragmentation. There are 2208 or so characters in 879!. Assuming that it gradually allocated smaller pieces in the process of getting there, it's a bit of a surprise it got that far. Allocating gradually increasing chunks of memory is a classic way of fragmenting it.

It's a little gratifying it got that far. In any case, I would think the use for it might be in less "tortuous" situations where you just need larger numbers than longs, or more precision than standard floats.

I wonder how far can you go with a PC ( with the latest Pentium Chip ) ? An Assembly ? a C++ ? Java ? Hum...

Pretty impressive for a 8 bit , 16 Mhz microcontroller...

In any case, I would think the use for it might be in less "tortuous" situations where you just need larger numbers than longs, or more precision than standard floats.

Arduino does support the type long long or int_64 type - avr-libc: <stdint.h>: Standard Integer Types -

Absolutely it does. However it generates a fairly massive amount of code to do arithmetic for the long long type. And long long doesn't have decimal places.

I have updated the BigNumber library to have a C++ wrapper. The updated library is (still) at:

http://www.gammon.com.au/Arduino/BigNumber.zip

The "raw" library was rather fiddly to work with, as it used extensive memory allocations to handle the numbers. This unfortunately is necessary because of the nature of the numbers, you don't know until runtime how large they are going to get.

The C++ class handles allocation and deallocation in the constructor and destructor.

For example, factorials can be produced with more "natural" looking code, like this:

  BigNumber::begin ();  // initialize library
 
  //factorials
  BigNumber fact = 1;

  for (int i = 2; i <= 200; i++)
  {
    Serial.print (i);
    Serial.print ("! = ");
    fact *= i;
    printBignum (fact);
  }

The normal arithmetic operations are supported (eg. assignment, add, subtract, divide, multiply, modulus). Also things like a++ or a--.

Also comparisons can be done in natural way.

The only memory allocation you have to worry about is when you get a number to print. Since the library may have to return any size number, it does a malloc to store the number (plus a sign, and decimal point if required). It is up to you to free that string. eg.

// function to display a big number and free it afterwards
void printBignum (BigNumber n)
{
  char * s = n.toString ();
  Serial.println (s);
  free (s);
}  // end of printBignum

An important parameter is the "scale" of the number, which you can set with setScale (n). The scale is effectively the number of decimal places.

For example:

  BigNumber::begin ();  // initialize library

  BigNumber a, b = 2, c;
 
  BigNumber::setScale (0);
  a = BigNumber (1) / BigNumber (3);
  c = b.sqrt ();
  Serial.print ("1/3 = ");
  printBignum (a);
  Serial.print ("sqrt(2) = ");
  printBignum (c);

Output:

1/3 = 0
sqrt(2) = 1

Change the scale to setScale (20) and we get:

1/3 = 0.33333333333333333333
sqrt(2) = 1.41421356237309504880

Change the scale to setScale (100) and we get:

1/3 = 0.3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
sqrt(2) = 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727

So clearly the scale is affecting the results. Note that, of course, the larger the scale the slower the calculation and the more memory it will require.

Some caveats:

• Working with large numbers is necessarily slow - the larger the number, or the more decimal places, the slower.
• Each digit requires a byte of memory, plus some overhead (eg. where the decimal point is) - large numbers will soon gobble up the available memory.
• Doing a toString also requires memory - a byte per digit, plus the sign, decimal point, and trailing 0x00 byte.
• An "error" condition inside the library (eg. running out of memory) calls exit(), effectively sending the library into a tight loop.
• You may need to cast some numbers to avoid "ambiguous" warnings from the compiler.
• If you only have 2048 bytes of RAM, you clearly need to use a library like this with caution. Running out of memory will be quite likely unless you closely manage the size of your numbers, and how many you have.
• Memory fragmentation will quite possibly be a problem, particularly if you calculate numbers of different sizes (eg. factorials).

The supplied library now has some example code (eg. powers, factorials, sine calculations, e^x, and ln(x) ).

Any helpful suggestions welcome, including better algorithms for things like sine, cosine etc.

Note that cosine and tangent can effectively be calculated from the sine.

Baha! That is so cool, had to try it just to watch that little bitty machine crunch out those big numbers!

Oh hey, anyone know anything about this blue smoke?

I played with the Calculate_E sketch a bit and got 192 decimal places out of an Uno. I checked the result against http://apod.nasa.gov/htmltest/gifcity/e.2mil and it was good. The last two or three places were off, but that is the nature of the computation and is independent of the number of digits calculated. So just a little caveat there before cutting any lumber to length.

Again, super job, Nick!

You could make printing less RAM hungry by implementing another interface to the bignum which fetches max 9 digits at the time as this would fit in a unsigned long. The code below is far from complete (esp fractional part) and not checked but you should get the idea. Greatest advantage is that there is no need to allocate a long string anymore as the number is printed in chunks and there is no free() needed to.

What do you think of it?

void printBignum (BigNumber n)
{
  Serial.print( n.sign );   
  for (int i=0; i<n.length; i++)
  {
    Serial.print( n.digit(i) );
  }
} 

or 

// additional wrapper functions with less params can be added
// separator can be any char but mostly a "dot comma, space ,...."
// chunksize must between 1 and 9, mostly 3 or 5 
void printBignumWirhSeparator (BigNumber n, uint8_t chunksize, char separator)  // e.g 12.345.678.901.234.567.890
{
  Serial.print( n.sign ); 

  int p = n.length  % chunksize;
  Serial.print( n.digit(0, p) );
  for (int i=p; i<n.length; i+=chunksize)
  {
    Serial.print(separator);  // default .
    Serial.print( n.digit(i) );
  }
} 

==================

long digit(int n)
{
  return digit(n, n+1);
}

long digit(int begin, int end)
{
  long value = 0;  
  // if (NOT VALID PARAMS) return -1;  // to be elaborated
  if (e <= b) e = b+1; // at least one digit
  if (e > b+9) e = b+9;
  for (int i=b i<e; i++)
  {
    val = 10*val + (int)nptr[i];
  }
  return val;
}

Another option is to hand over the address of the print function to be used the BigNum class something like bignum.do_print( &Serial.print() );
did not elaborate that ..

Thanks for the supportive feedback everyone!

Yes you could probably improve on fetching numbers for outputting, although you are possibly trading off saving RAM by losing PROGMEM. It might be an individual choice which you are running out of.

Already it supports getting back a long:

  // for outputting purposes ...
  char * toString () const;  // returns number as string, MUST FREE IT after use!
  operator long () const;

So, if you happen to know the number fits into a long you can just access it directly, as in:

BigNumber a = "123456";
long foo = a;

You are right Rob, that simply having a print function that gets called by the main routine (eg. Serial.write) would let the library "output" its stuff without having to allocate memory.

Absolutely amazing library Nick. This is so useful! Thank you :).

I'm not sure if I am the first to notice this but I think there is a memory leak in the function bc_sqrt() in number.c for numbers less than 1.

The following code quickly crashes my Arduino Mega 2560 (Note: the MemoryFree library is used to confirm this is a memory leak).

#include <MemoryFree.h>
#include <BigNumber.h>

int calculationScale=5;
BigNumber test;

void setup() {
  Serial.begin(9600);
}

void loop() {
  Serial.print("freeMemory()=");
  Serial.println(freeMemory());
  BigNumber::begin (calculationScale);
  test = BigNumber("0.5").sqrt(); // sqrt of number < 1
  //printBignum(test);
  BigNumber::finish ();
}

// function to display a big number and free it afterwards
void printBignum (BigNumber n)
{
  char * s = n.toString ();
  Serial.println (s);
  free (s);
}  // end of printBignum

To fix this memory leak it is sufficient to free guess before declaring it a copy of one on line 1348 of number.c.

  /* Calculate the initial guess. */
  if (cmp_res < 0)
    {
      /* The number is between 0 and 1.  Guess should start at 1. */
      bc_free_num (&guess); // fix memory leak
      guess = bc_copy_num (_one_);
      cscale = (*num)->n_scale;
    }

I am new to c (and to pointers) but I think the issue is that bc_init_num(&guess) declares guess a copy of zero (thus incrementing zero's n_refs) but then guess is declared a copy of one before freeing it. If I understand correctly this means that each time bc_sqrt() is called on a number less than 1 zero will not be properly freed and will remain in memory. I have checked the library for this issue elsewhere and this seems to be the only place it occurs. Have I made a mistake here or is this a genuine fix?

Also, I have been collecting some useful arbitrary precision trig functions in a library so far I have: sin,cos,arcsin,arctan,arctan2. It is not at all optimised (for example it frequently multiplies by -1; it redeclares its own constants for 0,1,2,pi; it does not make use of pow where it should; many functions are declared in a lazy way). Given this warning, if anybody is still interested it is available here. Feel free to use and improve this library but please do post back any improvements you make and bugs you spot!

Cool library. It is working great on an atmega1284 - I am currently up to 1200 factorial and it is still going!!!

Edit: Just gone passed 1500! and still going.

Edit2:
It got to 1768! and then stopped

1768! = 54808057071290192252743298498199891842054545077729159091490353239717379775083354377195550235177675288341692009711122122454930544628743017398656002640621375821235089523815723487448866397750004326559557856225543057310009384474831846484262259483216015023062936120599925506577063072310585779262873197354532040505420868805697848584939180713757057408602084665615277261475016463892340037250161469261684804521622383774829010232263279050170264796684557391339168742343956384906476618586255207677885164533457772477484189243506455512324503924597684535910767748820335473249637415994146881063393422568871357578610345874171053749239928356651073971098303308155151717270099599517822008959636765999555305915099299329075366301499824489821070351217525299009374815246453576779316864526951006577275189967221046113143604057814252622924524879908310494113446651628024885326168268616078985847153165740041941716820774712052977081373021389649950641991182839522935608644919737050520490994489513809194732260695437733079544284499689438219770014369085947711526109789387841803168712042349304024098481763921988719842632501285445445868310641865391003565101514277195128520183270350695401537975204624945817438304834447604063777722759965010315696832332747077757898321054316150336650622008826436261652254690652991372558045946239898212162369022218222805968811848433639160889851390751580216902245738050218139881270279810832041440224262933684142174824133909694800750108453327144416390996386824093892410313547794441668286131551793361519408499717384930392517424990890424658793113138491426741980120319226750986935721993893833186784210301770283348509334430057738953774437798210574156016845011024968801000236548116803149221483908122736718056138680946640627712814643339981883777962659119663600314494709587740501123453606332487657573445312862940264724311960607498481568789679495427089423260701580953796111330047820931256885050021445721847646948324113819372468404561385451573316675348039811247174839242450634119045016344208777074842742471135195442842162911844957260120927626403871780317202278132074505536007572693966788689234804361310540380466668243411416716008281342815616816758235008489114773553074161942446353875723779525601855770760406612243466347050326094850070611823663536664973747207305652999045531489181432122193324671478951619056932475152870301737605199924965350212679900807430919041591159738999247838655163614460312582933241713955605286290159894705741095182586799708194021582492076781779792101294979612058201246647823414725791685791230584356908493907582096083731130936120385273726141641848354339720194673116144978882829781223262663458832244913132958990556853154238130292235817289102334406846983820687068471284649477755649621570434858991340042169142133898976688711523961423470887673721454366762690537583398942950843205842514294691762149459325488311501332777039832437484844358168424312566785188468356923205707483448843927738251752890157755570725637344073212103893287831685177065487213482149485400716880043274503478945042883622780669967123307077966563118971398119460658934359041205672758886919886834944372331466845019399516488074751957191329134962254714989679765677465758385088877391463689818673062801207017286754462894121968240224399636135535418868909320922671404805178546004831406297218653069966084615984888822297565419422729466887189516867577051244135657933999466656740178894899443356673352566295808064384421135924564033256332314875165493833106824464649632580936509556353837893204229852166190507041546614800002896704509630138336718168961148286586461145926676793465604309082842206716565554946415318412409412907217994054000353426738638848533396954907008226515074371597447683347381971388924543765695113455371056057748303029606308523192603465804787828083111763778473391283186406495520902363132449988022065166926732775126744574556258040147995955374495746930329812897328106931326431974120654283842600727916009199224598008724394375529382278706780241983861354454276731719826300536677356453066899357941319712527957721549412531989767290981694881915955764992954129548527818115822330462444094389060353190583842953962828467036060184341296887689970190461038893033035076168847348212817162411690410102448679836865631115216900453330520662478843527070365333896112923410016668463155043440315452471958668787317527170578193437102123061614321187350647027912492182611370611385163653458446822687728015026880552425098846043367245688521266693527234125292210280000827243523817242999396682446280938935246569884132043315943554785328454604826170005054493723196412574240321978280164951940322944183870464983040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1769! =

Bob101:
I am new to c (and to pointers) but I think the issue is that bc_init_num(&guess) declares guess a copy of zero (thus incrementing zero's n_refs) but then guess is declared a copy of one before freeing it.

Your argument seems sound to me. I've incorporated that line into my copy. Maybe there is another way of fixing it but yours seems fine.

Absolutely amazing library Nick. This is so useful! Thank you.

You are welcome! It's fun to see what you can do with a tiny processor.

Thanks for that Nick, a very speedy response!

On the surface it looks like my code is working nicely now all hail the BigNumbers.

If only our masters at Arduino.cc could be so forthcoming with fixing the known memory leak with free(). Maybe it is their way of implementing the fail fast principle XD.

The have tens of thousands of users. They need to carefully test in case the next release is worse than the previous one.