Go Down

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

#### nickgammon

##### Jan 04, 2012, 06:22 amLast 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).
Please post technical questions on the forum, not by personal message. Thanks!

#### nickgammon

#1
##### Jan 04, 2012, 08:03 amLast 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.
Please post technical questions on the forum, not by personal message. Thanks!

#### Techone

#2
##### Jan 04, 2012, 08:38 am
That is impressive....

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

Still impressive...

#### robtillaart

#3
##### Jan 04, 2012, 09:48 pm

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

#4
##### Jan 05, 2012, 12:23 am
I just tried it out on a Mega
Code: [Select]
877! = 1011611483741808350979735614596014894238217322814495678061885986476300120788475589798361596687802128663578042330388633117314918769911893358399855960767087128402653443885249004974897395365479609012783486035483721056839305679987543322025849969875662030830862782926142893333372401656801048774838842075152998418255972797905783699836709546309855893192339084006473628589802797018620887820660848933680457891211257009195751003942681086243147771699300541509917023520768906796204790094872374055294488039306715002830688899997703266103221933805878232123922606100282667038975335043142164163282886560774853187972831209054672730754941302295267776051816732092387029190871291957841784343189241963815856213180566177167112195639046498955376116343921497000536730892516289134843911964047782503358856762108229999177212919928477847641247924465566305875742648991423035640465076829096936501640889769710663169426265396877392790851591894194592057595867010347648202135987859552881929151183698789144026592022450651849397915054771736000737211818458904512736028771559016796149604022595483819743035778947290107102852122610304080676169477575467029871046405065014560927549248111540931483826114271560342485211947257026936230866153767287913951996901524008773010016174894707271992213946054234643582296721076221917553548823648235881143398824484971152482893217762115260242215038066422004691931201792687326732904794242502893084554255994244841293557872138759903613572361115372118957926480182881795156632473733548929885690977865413771097341102912144355671697711537730972632264019256588811705253789509886640902406984090032313082820615025013367001560652771755174854201473950778204978987557794358451512535545900895512531104615368723488464504058808076406951191668900760904086410146183739769732997767263632442026777218726524601613206446515770406124734920046269981962123073162988129456830952669379413202410563973619772261016585559412160000284936236613564082779335945761084993654032138109517877957056794329153855895700267217477802393600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
878! = 888194882725307732160207869615301077141154809431127205338335896126191506052281567842961481891890268966621521166081219877002498679982642368675073533553502498737529723731248626367959913130891096713223900739154707087904910387029063036738696273550831263069497523409153460346700968654671320824308503341984332611228744116561278088456630981660053474222873715757683845901846855782349139506540225363771442028483483654073869381461673993721483743551985875445707146651235100167067805703297944420548560498511295772485344854197983467638628857881561087804804048156048181660220344167878820135362374400360321099040145801550002657602838463415245107373495090777115811629584994338985086653320154444230321755172537103552724507771082826082820230149963074366471249723629301860392954704433953037949076237131025939277592943697203550229015677680767216558902045814469425292328337455947110248440701217805962262756261018458350870367697683102851826569171235085235121475397340687430333794739287536868455347795711672323771369418089584208647271976606918162182233261428816747019352331838834793734385413915720714036304163651846982833676801311260052226778743647082784494388239841932937842799328330429980702016089691669650010700483007678788449853279538079702702794201557552984809163844635618017065256521104922843612015867163151103643904167897804671879980245195137198492664803422318520119515595173979472871490409344917540128238636762946970655743811737831195372716533059296720445059449600570216147523311938055960439636678565833291023465488356862744279750590730127793971127808907284976677212827189680470712313332031048370886716499991961736227370253133601043521988894128783263971551075743446720428006209300986260002309852293739222871834563633491085303146285294868073787868108349323517825572039657469284099510398041888600216395260040846416577517259800625044162744058237103577663097576443715124791716475168838160045172562121163876480250174015746709264680256960378232624428240217260156696846295865420997085476424834616945510501580800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
879! = 780723301915545496568822717391849646807075077489960813492397252694922333819955498133963142582971546421660317104985392271885196339704742642065389635993528696390288627159767542577436763642053274010923808749716987530268416230198546409293314024451180680238088323076645891644750151447456091004567174437604228365270066078457363439753378632879187003841905996151004100547723386232684893626248858094755097543036982131930931186304811440481184210582195584516776581906435653046852601213198893145662184678191428984014618126840027468054354766077892196180422758329166351679333682523565482898983527097916722246056288159562452336032895009342000449381302184793084798422405210023967891168268415756478452822796660114022844842330781804126798982301817542368128228507070156335285407185197444720357238012438171800625004197509841920651304780681394383355274898270918624831956608623777509908379376370451440828962753435224890415053206263447406755554301515639921671776874262464251263405575833744907372250712430559972595033718500744519400952067437481064558183036795929920630010699686335783692524778831918507637911359849973497910801908352597585907338515665785767570567262821059052363820609602447953037072142838977622359405724563749655047421032713972058675756103169089073647255019434708237000360482051227179534961947236409820102991763582170306582502635526525597475052362208217979185054208157927956654040069814182517772721761714630387206398810517553620732617832559121817271207256198901219993672991193551189226440640459367462809626164265682352221900769251782330900621344029503494499270075099729133756123418855291518009423803492934366143858452504435317255828237939200489030993395578489667256217457975566922542030360166196776904342581433838663981465584774189036859536067239055372168677822858915500723469639878820079590211433575904000171637671364749413819052027190414044765862769694025594691918781673408742679706682104503047426139902959841357443653945868172466476872423150971677736527894065705056438133777429628295103730889523200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
880! =     hang :-(

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

#### stimmer

#5
##### Jan 05, 2012, 12:37 am
Spoke to soon, it only got to 3185

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

#### nickgammon

#6
##### Jan 05, 2012, 05:30 am
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.
Please post technical questions on the forum, not by personal message. Thanks!

#### Techone

#7
##### Jan 05, 2012, 05:52 am
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...

#### robtillaart

#8
##### Jan 05, 2012, 08:06 am
Quote
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 - http://www.nongnu.org/avr-libc/user-manual/group__avr__stdint.html -
Rob Tillaart

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

#### nickgammon

#9
##### Jan 05, 2012, 10:53 am
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.
Please post technical questions on the forum, not by personal message. Thanks!

#### nickgammon

#10
##### Jan 06, 2012, 11:15 pmLast Edit: Jan 07, 2012, 06:28 am by Nick Gammon Reason: 1
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:

Code: [Select]

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.

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

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

Code: [Select]
1/3 = 0
sqrt(2) = 1

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

Code: [Select]
1/3 = 0.33333333333333333333
sqrt(2) = 1.41421356237309504880

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

Code: [Select]
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.
Please post technical questions on the forum, not by personal message. Thanks!

#### JChristensen

#11
##### Jan 07, 2012, 01:36 am
Baha! That is so cool, had to try it just to watch that little bitty machine crunch out those big numbers!

#### JChristensen

#12
##### Jan 07, 2012, 02:15 am
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!

#### robtillaart

#13
##### Jan 07, 2012, 04:29 pm

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?

Code: [Select]

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

Rob Tillaart

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

#### nickgammon

#14
##### Jan 07, 2012, 11:01 pm
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:

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

Code: [Select]
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.
Please post technical questions on the forum, not by personal message. Thanks!