Pages: [1] 2 3 ... 8   Go Down
Author Topic: Arbitrary precision (big number) library port for Arduino  (Read 14563 times)
0 Members and 1 Guest are viewing this topic.
Global Moderator
Offline Offline
Brattain Member
*****
Karma: 474
Posts: 18696
Lua rocks!
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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:
#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:
--- 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:
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).
« Last Edit: January 04, 2012, 05:49:03 am by Nick Gammon » Logged

Global Moderator
Offline Offline
Brattain Member
*****
Karma: 474
Posts: 18696
Lua rocks!
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Code:
#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:
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:
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.
« Last Edit: January 04, 2012, 06:02:37 am by Nick Gammon » Logged

Toronto, Canada
Offline Offline
Edison Member
*
Karma: 2
Posts: 1234
"Keep it R.E.I.L. - "Research, Experiment, Investigate and Learn"
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

That is impressive.... smiley-eek

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

Still impressive...
Logged

Global Moderator
Netherlands
Offline Offline
Shannon Member
*****
Karma: 212
Posts: 13531
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset


Well done Nick!

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

thanks,


Logged

Rob Tillaart

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

Offline Offline
God Member
*****
Karma: 32
Posts: 507
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I just tried it out on a Mega  smiley-grin
Code:
877! = 1011611483741808350979735614596014894238217322814495678061885986476300120788475589798361596687802128663578042330388633117314918769911893358399855960767087128402653443885249004974897395365479609012783486035483721056839305679987543322025849969875662030830862782926142893333372401656801048774838842075152998418255972797905783699836709546309855893192339084006473628589802797018620887820660848933680457891211257009195751003942681086243147771699300541509917023520768906796204790094872374055294488039306715002830688899997703266103221933805878232123922606100282667038975335043142164163282886560774853187972831209054672730754941302295267776051816732092387029190871291957841784343189241963815856213180566177167112195639046498955376116343921497000536730892516289134843911964047782503358856762108229999177212919928477847641247924465566305875742648991423035640465076829096936501640889769710663169426265396877392790851591894194592057595867010347648202135987859552881929151183698789144026592022450651849397915054771736000737211818458904512736028771559016796149604022595483819743035778947290107102852122610304080676169477575467029871046405065014560927549248111540931483826114271560342485211947257026936230866153767287913951996901524008773010016174894707271992213946054234643582296721076221917553548823648235881143398824484971152482893217762115260242215038066422004691931201792687326732904794242502893084554255994244841293557872138759903613572361115372118957926480182881795156632473733548929885690977865413771097341102912144355671697711537730972632264019256588811705253789509886640902406984090032313082820615025013367001560652771755174854201473950778204978987557794358451512535545900895512531104615368723488464504058808076406951191668900760904086410146183739769732997767263632442026777218726524601613206446515770406124734920046269981962123073162988129456830952669379413202410563973619772261016585559412160000284936236613564082779335945761084993654032138109517877957056794329153855895700267217477802393600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
878! = 888194882725307732160207869615301077141154809431127205338335896126191506052281567842961481891890268966621521166081219877002498679982642368675073533553502498737529723731248626367959913130891096713223900739154707087904910387029063036738696273550831263069497523409153460346700968654671320824308503341984332611228744116561278088456630981660053474222873715757683845901846855782349139506540225363771442028483483654073869381461673993721483743551985875445707146651235100167067805703297944420548560498511295772485344854197983467638628857881561087804804048156048181660220344167878820135362374400360321099040145801550002657602838463415245107373495090777115811629584994338985086653320154444230321755172537103552724507771082826082820230149963074366471249723629301860392954704433953037949076237131025939277592943697203550229015677680767216558902045814469425292328337455947110248440701217805962262756261018458350870367697683102851826569171235085235121475397340687430333794739287536868455347795711672323771369418089584208647271976606918162182233261428816747019352331838834793734385413915720714036304163651846982833676801311260052226778743647082784494388239841932937842799328330429980702016089691669650010700483007678788449853279538079702702794201557552984809163844635618017065256521104922843612015867163151103643904167897804671879980245195137198492664803422318520119515595173979472871490409344917540128238636762946970655743811737831195372716533059296720445059449600570216147523311938055960439636678565833291023465488356862744279750590730127793971127808907284976677212827189680470712313332031048370886716499991961736227370253133601043521988894128783263971551075743446720428006209300986260002309852293739222871834563633491085303146285294868073787868108349323517825572039657469284099510398041888600216395260040846416577517259800625044162744058237103577663097576443715124791716475168838160045172562121163876480250174015746709264680256960378232624428240217260156696846295865420997085476424834616945510501580800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
879! = 780723301915545496568822717391849646807075077489960813492397252694922333819955498133963142582971546421660317104985392271885196339704742642065389635993528696390288627159767542577436763642053274010923808749716987530268416230198546409293314024451180680238088323076645891644750151447456091004567174437604228365270066078457363439753378632879187003841905996151004100547723386232684893626248858094755097543036982131930931186304811440481184210582195584516776581906435653046852601213198893145662184678191428984014618126840027468054354766077892196180422758329166351679333682523565482898983527097916722246056288159562452336032895009342000449381302184793084798422405210023967891168268415756478452822796660114022844842330781804126798982301817542368128228507070156335285407185197444720357238012438171800625004197509841920651304780681394383355274898270918624831956608623777509908379376370451440828962753435224890415053206263447406755554301515639921671776874262464251263405575833744907372250712430559972595033718500744519400952067437481064558183036795929920630010699686335783692524778831918507637911359849973497910801908352597585907338515665785767570567262821059052363820609602447953037072142838977622359405724563749655047421032713972058675756103169089073647255019434708237000360482051227179534961947236409820102991763582170306582502635526525597475052362208217979185054208157927956654040069814182517772721761714630387206398810517553620732617832559121817271207256198901219993672991193551189226440640459367462809626164265682352221900769251782330900621344029503494499270075099729133756123418855291518009423803492934366143858452504435317255828237939200489030993395578489667256217457975566922542030360166196776904342581433838663981465584774189036859536067239055372168677822858915500723469639878820079590211433575904000171637671364749413819052027190414044765862769694025594691918781673408742679706682104503047426139902959841357443653945868172466476872423150971677736527894065705056438133777429628295103730889523200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
880! =     hang :-(  

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


Offline Offline
God Member
*****
Karma: 32
Posts: 507
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Spoke to soon, it only got to 3185 smiley-sad

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


Global Moderator
Offline Offline
Brattain Member
*****
Karma: 474
Posts: 18696
Lua rocks!
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Toronto, Canada
Offline Offline
Edison Member
*
Karma: 2
Posts: 1234
"Keep it R.E.I.L. - "Research, Experiment, Investigate and Learn"
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Global Moderator
Netherlands
Offline Offline
Shannon Member
*****
Karma: 212
Posts: 13531
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Rob Tillaart

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

Global Moderator
Offline Offline
Brattain Member
*****
Karma: 474
Posts: 18696
Lua rocks!
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Global Moderator
Offline Offline
Brattain Member
*****
Karma: 474
Posts: 18696
Lua rocks!
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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:
 
  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:
// 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:
 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:
1/3 = 0
sqrt(2) = 1

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

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

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

Code:
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.
« Last Edit: January 07, 2012, 12:28:27 am by Nick Gammon » Logged

Grand Blanc, MI, USA
Offline Offline
Faraday Member
**
Karma: 93
Posts: 3968
CODE is a mass noun and should not be used in the plural or with an indefinite article.
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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

MCP79411/12 RTC ... "One Million Ohms" ATtiny kit ... available at http://www.tindie.com/stores/JChristensen/

Grand Blanc, MI, USA
Offline Offline
Faraday Member
**
Karma: 93
Posts: 3968
CODE is a mass noun and should not be used in the plural or with an indefinite article.
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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

MCP79411/12 RTC ... "One Million Ohms" ATtiny kit ... available at http://www.tindie.com/stores/JChristensen/

Global Moderator
Netherlands
Offline Offline
Shannon Member
*****
Karma: 212
Posts: 13531
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset


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


Logged

Rob Tillaart

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

Global Moderator
Offline Offline
Brattain Member
*****
Karma: 474
Posts: 18696
Lua rocks!
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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

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