Go Down

Topic: Arbitrary precision (big number) library port for Arduino (Read 17 times) previous topic - next topic

Nick Gammon

Jan 04, 2012, 06:22 am Last Edit: Jan 04, 2012, 11:49 am by Nick Gammon Reason: 1
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:

Code: [Select]
#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:

Code: [Select]
--- 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:

Code: [Select]
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).

Nick Gammon

#1
Jan 04, 2012, 08:03 am Last Edit: Jan 04, 2012, 12:02 pm by Nick Gammon Reason: 1
Just as another example, you can calculate "e" to around 100 digits like this:

Code: [Select]
#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:

Code: [Select]
2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274240

Time to execute: around 4 seconds.

(edit)

Theory:

http://en.wikipedia.org/wiki/E_%28mathematical_constant%29

E can be calculated as:

Code: [Select]
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.

Techone

That is impressive.... :smiley-eek:

Really.... !!! and 12K inside the chip...  :smiley-eek:

Still impressive...

robtillaart


Well done Nick!

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

thanks,


Rob Tillaart

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

stimmer

I just tried it out on a Mega  :D
Code: [Select]
877! = 1011611483741808350979735614596014894238217322814495678061885986476300120788475589798361596687802128663578042330388633117314918769911893358399855960767087128402653443885249004974897395365479609012783486035483721056839305679987543322025849969875662030830862782926142893333372401656801048774838842075152998418255972797905783699836709546309855893192339084006473628589802797018620887820660848933680457891211257009195751003942681086243147771699300541509917023520768906796204790094872374055294488039306715002830688899997703266103221933805878232123922606100282667038975335043142164163282886560774853187972831209054672730754941302295267776051816732092387029190871291957841784343189241963815856213180566177167112195639046498955376116343921497000536730892516289134843911964047782503358856762108229999177212919928477847641247924465566305875742648991423035640465076829096936501640889769710663169426265396877392790851591894194592057595867010347648202135987859552881929151183698789144026592022450651849397915054771736000737211818458904512736028771559016796149604022595483819743035778947290107102852122610304080676169477575467029871046405065014560927549248111540931483826114271560342485211947257026936230866153767287913951996901524008773010016174894707271992213946054234643582296721076221917553548823648235881143398824484971152482893217762115260242215038066422004691931201792687326732904794242502893084554255994244841293557872138759903613572361115372118957926480182881795156632473733548929885690977865413771097341102912144355671697711537730972632264019256588811705253789509886640902406984090032313082820615025013367001560652771755174854201473950778204978987557794358451512535545900895512531104615368723488464504058808076406951191668900760904086410146183739769732997767263632442026777218726524601613206446515770406124734920046269981962123073162988129456830952669379413202410563973619772261016585559412160000284936236613564082779335945761084993654032138109517877957056794329153855895700267217477802393600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
878! = 888194882725307732160207869615301077141154809431127205338335896126191506052281567842961481891890268966621521166081219877002498679982642368675073533553502498737529723731248626367959913130891096713223900739154707087904910387029063036738696273550831263069497523409153460346700968654671320824308503341984332611228744116561278088456630981660053474222873715757683845901846855782349139506540225363771442028483483654073869381461673993721483743551985875445707146651235100167067805703297944420548560498511295772485344854197983467638628857881561087804804048156048181660220344167878820135362374400360321099040145801550002657602838463415245107373495090777115811629584994338985086653320154444230321755172537103552724507771082826082820230149963074366471249723629301860392954704433953037949076237131025939277592943697203550229015677680767216558902045814469425292328337455947110248440701217805962262756261018458350870367697683102851826569171235085235121475397340687430333794739287536868455347795711672323771369418089584208647271976606918162182233261428816747019352331838834793734385413915720714036304163651846982833676801311260052226778743647082784494388239841932937842799328330429980702016089691669650010700483007678788449853279538079702702794201557552984809163844635618017065256521104922843612015867163151103643904167897804671879980245195137198492664803422318520119515595173979472871490409344917540128238636762946970655743811737831195372716533059296720445059449600570216147523311938055960439636678565833291023465488356862744279750590730127793971127808907284976677212827189680470712313332031048370886716499991961736227370253133601043521988894128783263971551075743446720428006209300986260002309852293739222871834563633491085303146285294868073787868108349323517825572039657469284099510398041888600216395260040846416577517259800625044162744058237103577663097576443715124791716475168838160045172562121163876480250174015746709264680256960378232624428240217260156696846295865420997085476424834616945510501580800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
879! = 780723301915545496568822717391849646807075077489960813492397252694922333819955498133963142582971546421660317104985392271885196339704742642065389635993528696390288627159767542577436763642053274010923808749716987530268416230198546409293314024451180680238088323076645891644750151447456091004567174437604228365270066078457363439753378632879187003841905996151004100547723386232684893626248858094755097543036982131930931186304811440481184210582195584516776581906435653046852601213198893145662184678191428984014618126840027468054354766077892196180422758329166351679333682523565482898983527097916722246056288159562452336032895009342000449381302184793084798422405210023967891168268415756478452822796660114022844842330781804126798982301817542368128228507070156335285407185197444720357238012438171800625004197509841920651304780681394383355274898270918624831956608623777509908379376370451440828962753435224890415053206263447406755554301515639921671776874262464251263405575833744907372250712430559972595033718500744519400952067437481064558183036795929920630010699686335783692524778831918507637911359849973497910801908352597585907338515665785767570567262821059052363820609602447953037072142838977622359405724563749655047421032713972058675756103169089073647255019434708237000360482051227179534961947236409820102991763582170306582502635526525597475052362208217979185054208157927956654040069814182517772721761714630387206398810517553620732617832559121817271207256198901219993672991193551189226440640459367462809626164265682352221900769251782330900621344029503494499270075099729133756123418855291518009423803492934366143858452504435317255828237939200489030993395578489667256217457975566922542030360166196776904342581433838663981465584774189036859536067239055372168677822858915500723469639878820079590211433575904000171637671364749413819052027190414044765862769694025594691918781673408742679706682104503047426139902959841357443653945868172466476872423150971677736527894065705056438133777429628295103730889523200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
880! =     hang :-(  


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

Go Up