how to calculate 55^5000 ???

[scifire]

hi guys
i have to calculate an expression like follow :
55^5000 or something like that a VERY BIG NUMBER but how to do it i can't write any code to solve this proble is there is a program or a lib that can do it for me ! i have solve the problem but for expressions like x^1000 where x is a 2 digit number and my pentium II @ 400 do it for me about 1 min :( for greater numbers my code do not apply :(
please any help

[bwkaz]

Lisp does bignums by default, so you can do something like:

(defun pow (x y) ; x to the yth power
(if (eq y 0)
1
(* x (pow x (- y 1)))
)
) Then, you would evaulate (pow 55 5000) to answer your question. It'll take a while, because multiplying 55 by itself five thousand times is going to take a while on a 400MHz machine. It takes a while on my Athlon XP2500, for goodness' sake...

Of course, there are more efficient algorithms than what I've used here -- there's one that I'm fairly sure is valid, and takes about log-base-2-of-y iterations (rather than the y iterations that my algorithm takes). But it's not quite as straightforward. There is also a way to rewrite my version to be tail-recursive, so that the Lisp runtime would be able to evaluate it using a for loop instead of 5000 recursive function calls. That would also help the speed a little (though not as much as using a big-Oh-log-n algorithm would).

If you need to use C, then maybe the GMP library would be a good one to look into. It allows arbitrary-precision math to be done.

[Strogian]

2^10 = 1024
2^20 = 1048576
2^21 = 2097152
55^1000 = 2858068855718481985
~$ cat f.c
#include <stdio.h>

unsigned long long the_power(int base, int exp)
{
unsigned long long ans=base;
int e=1;
while (e*2 < exp) {
ans *= ans;
e *= 2;
}
if (e == exp)
return ans;
else
return (ans * the_power(base, exp - e));
}

int main()
{
int base=2, exp=10;
printf("%d^%d = %lld\n", base, exp, the_power(base, exp));
exp=20;
printf("%d^%d = %lld\n", base, exp, the_power(base, exp));
exp=21;
printf("%d^%d = %lld\n", base, exp, the_power(base, exp));

base=55; exp=1000;
printf("%d^%d = %lld\n", base, exp, the_power(base, exp));

return 0;


It finishes instantly on my system, but the 55^1000 answer is definitely wrong. So yeah, you'll still want a bignum library.

[chris_i386]

You could use the GNU bc program.
If you use a mainstream Linux distro, it should be already installed.

chris@probus:~> echo 55 ^ 5000 | bc
65079989053955269949805985424446369521637103961454 653379789799381889\
73018434051225038862976703422784672837355401863895 299170077466134211\
30555740854024669495317724190305184278798721593698 973942082004442685\
42903057282086342117810423058263674415535816951411 402162281337893148\
73758314006183779306984742487062295205117977067076 266355740454535440\
71837710036550445861609795176025444144574085892232 907413200801341865\
25212913710449799072638035705346460330311412754230 747319800898512322\
18718848062841611423374341419530461989759365018547 103506892844242688\
48499172380089299099510082625783339098705626699337 045438633985833064\
34322799422028435713317499763312569320778218981287 372103258581252777\
18192987256431741782205020857716244930074735577109 159386156496045591\
82412489512359655865576764330619105914489229749005 942775857839823488\
90849842575749983046787824001265956214575497280417 946895024244678012\
05395162538719115115640499824614397431331216562507 167251556143293601\
35428431202792283746570622918980753060606454465709 192246427583566879\
75992494862195352876345239636735307873131649345329 918575695564717331\
72288423448644315620371032502632533352319813979672 371119207530363087\
27167385888808749979129770288205939527630293501545 584850932744898211\
22765691653910308631031126017285566596007737574603 247737090848944496\
99047464074325943587032834985520239110258584305529 410498890255301658\
70073358980369620519976909269264649478385437214346 728134641665421061\
00135369542745299189735051221634805423798456124339 182536916665425397\
18767592694160717686727446918021821682841630105300 931220641003379226\
04534156717035584612205935564707012508549260995719 327453618052112692\
96800941335945314049464885273591966304085027535007 689837104395641543\
24426059791561238681511122566719834694528311968713 969911408789716899\
70891410638137987635141244037452649580682066769364 958779997022245352\
56029520627952170892963839819501837322171520291793 286578038408187412\
08115608042398299149032290077235324482984737769787 246846520486900588\
83459240527871058451810401598368299927384722806285 557142310660602388\
01821999488785831643937328177226655031630907637072 991711557395800270\
40189330351008669130628965676174738511112105369388 862711540700765567\
10094261613790131848832385560771948667523164217016 020066768627884804\
56492678196101821325604759094730593443341835655905 596825577454230247\
30540172613700354530024919564555314845121164550140 416000527464447969\
24315133084208450868602870448993807346430803702089 286644493252757389\
07088898056593373879403064907807502713421443034510 889673031873091981\
80624240150157638051844908503807682407038909871136 117908657538362822\
84534876264489761572924496367119581625859180062838 047860536642062235\
50951231574999259177548151860662212452480905794686 444451286678426434\
63082453968752656299738543159873124984975272845057 108960233377806887\
44617473284915645430784722033674983041223831749109 897910279713717020\
51666683562198018438500027981597007329328309161363 232378653510012385\
42077097971926526991423696161488951866079016158501 983513027527710676\
12448884260337800033789307917429832867853040534321 582672890238139698\
96123418525925394058479791526637198039143849851223 921634228326002796\
56249073019365695381191760775817403987288292804700 889436818605065171\
76725237937488069595108538451779425936767180558784 503896190532299114\
36429464257431314044080661652145985035216747793231 550132901381807298\
59086632311018673464079648555387999443666646956873 572183579197198100\
49328094571275045595256716375329037997999383200110 910566080087412271\
47083175928166942896755770758183253482676144233329 547918599445102066\
93191676101374091074027554861568681707830720854032 359697844587899686\
80073020478055070298678060163694102334914907052457 331198185914858583\
59274481227260323606370235010072735155272994326786 954677755707123344\
56140623236688469919122289222158691860466981036447 560442682359946044\
39054589264841243666479653093615347768993848162583 384705582963407930\
26443671906625159205819090085134174391469682889298 116020969222034438\
09645340245001811674864043667890792313365997712685 997224384709770419\
49164067053559044654645603019022579154365481648819 577476984845506689\
54773524852086060724213551639322338263606477302835 114500631317867730\
62776331746101876338024450514472893473255607131429 755774257303487362\
33064322109108227158325364783428242887191845362509 865012217846109542\
49323831013007136561342232417520179161686686555810 528265132253928378\
87612965522611386579932436705853852212327737313758 230606770123092819\
71124009521321447583405787760575119932306531575659 012045553919901453\
88722859167161715882023639410544003440544624981333 556293076062558475\
75269263779481097301657022540620059877778548615040 979128053811820955\
88711497932419827278057795707983327215461274481427 039817019353391689\
37823090630365331796833276472686850938747304534096 599837238045231875\
80871521480761782148801209980541228564837575955922 212271891272601438\
62145106438952921266919357666693567544645793161220 413038872200062396\
26570118342739591442752599358069608634039270388678 023730658714779436\
14719320093275745340511491238207664452096352258589 837420394074819995\
41530052394405211329281461312929329575880183889622 356179752827012323\
00638310108494187664513735330045648999020132425964 998003728732521275\
29685893615278705539219581531582825632308970468397 050473059296878081\
41974966825017735636890136830471255100934309439574 464531993241903941\
89976027525152960889296901739680914123450319773207 902133476268460494\
67984938280849145291723584881220496215108954724443 758610357004927826\
77264084708883841683962810524057816447322674963696 081923817274619178\
62031031861423597597425678611277781608090878681325 457267921545527239\
68633496241640390626599766988807555506966136059119 325501546066252188\
02977267251051081992370356039228751319300745815454 225058493179640724\
54460056194700572657684943292663397786563834446403 444585018957380355\
92913589268169067172418157513070630503235786954698 698960253056589784\
00067633967699901366640446944642640708849283292773 004695577988133661\
44191598588184942877759690079020028550993677199999 443683895495389473\
07785159610216846190836802232767725621536392466370 798053035583177472\
11741979030362887504563317975040789109419022653690 022064603802046957\
23979418590546023725298492325945379968015690305331 439999863823614647\
07283124377596060216503762572827751510793037906461 771743937440001532\
92739015415351155019271475886052462163761424588173 333293264170197395\
52436601229993998554689071504408916619054523583155 329614550886708107\
00355076847716646316809024296783949319326644773855 915343716001675991\
10226592749728041406254240648102544432306122720005 420608469176619670\
37121694769708295144070536914549147142109516594316 457651908662224777\
43302714790196681114585046946751508029016723740942 142990413797709913\
51480252454115796909374296553861854216231621687647 626258191282578947\
67627301813991476542761110826120813665442411781407 956638257044616536\
68922373366267262134671283217983902514820447239879 526921173854543188\
55862796705555052951887915721453260097241877136317 104899149378918744\
61373940512428307044274456748988277093135590286142 660564760769274014\
00897178685487819840352491754742173169984217415930 658933731628955643\
80905605089228598338211363837257832570239621890942 017930316347321620\
45661012127275447959315556420506964886417124193222 673173419621875351\
53879428779009560147419783820991825429517047241242 703643931015796974\
16334016419274403627097311792529808600587447270315 817634276243762457\
84762687440153747372967638021466318102262977406069 909652112704095151\
88324862919020323866837094470853233733659898233647 615772705487583385\
38731828482973314353070686035427113859865741412204 212454878221662293\
22498795769663323279578555512181054444619837792470 667965431689667565\
26955799550221003669636492854959475779152292650265 187395809126310983\
44259814137631805355568695397363187792033602024123 772826240901233687\
98810483958525845976157942544668537849811063197954 409828457474819051\
63107361459392934408654877145105567411775610871646 051174005586354989\
08513614307186753113306071010048555299686650681535 705297605009268898\
02061453734410952747418992643109484973373106621972 173319884030731858\
97429817495869148837350915822063420381687342634083 044609386461207345\
35630711674607916664278712983440263014196311979842 224748991433034258\
64518652349895982324088782934126814559346177656220 191463334100462633\
33519154493188400842305355722702908811025508732966 466136354862914618\
25524539888445346254308792941474391278343853340754 363884525519087175\
78747770557892885151020204747052973678490370269951 428280983251255084\
50875480332419338207554146056670369882447803473048 216958911233112603\
38469632827837416030725691534343737537946987578765 020189891185169043\
98728873567565571236274860552493095903077245042218 257256027388501686\
31061130604259126895187823752531031118451210204511 8808746337890625
chris@probus:~>

...That looks reasonable!

[bwkaz]

Well, it definitely does end in a 5, so yeah, I'd say there's a pretty good chance it's right... ;)

[Trogdor]

HAHA! It's that long in lisp and C++. Here it is in Pythonprint 55**5500

[Fryguy8]

java has a bignumber library as well.

[duncanbojangles]

I'm wondering if I got the wrong number. I tried "echo 55 & 5000 | bc" and the answer popped up instantly. I got the same answer, but I have an AMD K6-2 running at 475 MHz, so how does it come up with the answer so quickly? This is cool though, because now I can see how long it takes to find the largest prime number known. They found it a couple of weeks ago, and it is almost 6 and a half million digits long! And it is only the 40th Mersenne prime found, which takes the form (2^p) - 1, where p is a prime number. This is neat, now I'll find primes instead of putting my computer in "sleep" mode!

[cybertron]

...so how does it come up with the answer so quickly

We actually did exponent calculation algorithms in my beginning CS class last year, and if you use the O(log n) algorithm it goes pretty fast (I couldn't find a number in java that fit in a normal variable that it couldn't calculate almost instantly). Unfortunately, I can't find the source right now, but it was something like this (warning: completely untested code)


int intpow(int base, int exp)
{
if (exp == 0)
return 1;
if (exp % 2 != 0)
return base * intpow(base, exp - 1);
int x = intpow(base, exp / 2);
return x * x;
}


It's basically a recursive version of Strogian's code in a previous post, and of course you wouldn't use ints as the return type since bc is arbitrary precision. I'm sure that was a longer answer than you really wanted, but I have to put the stuff I learned in that class to use somehow :)

[bwkaz]

Originally posted by Trogdor
HAHA! It's that long in lisp and C++. Lisp does not have an exponentiation function built-in (at least, not that I know of). If it did, it would be something like:

(to-the-nth 55 5000) and you would be done. Same as your python example, same as a Java example.

C++ has an exponentiation function (named pow, in the C math library), but I it's only for doubles. To make one for bignums, you'd need a bignum library (at which point, exponentiation would surely be done for you already, and it'd be the same as your Python or a Java example also).

[o0zi]

In perl, it's:
print 55 ** 5500
as well, it does all the big number stuff automatically.