On Exponentiation By Squaring

I’ve been continuing to read and study number theory, and subsequently one thing that I do a lot of is raising large numbers to other large numbers. bc is a great tool for this, by the way, and it is able to return numbers that are many thousands of digits long.

Interestingly, prior to studying some of the algorithms that underpin some of the cryptography that all of use every day, I didn’t ever stop to think about exponentiation in terms of its computational costs, both in time and space.

Exponentiation

For example, let’s use a common base for the public key e that is used frequently in asymmetric encryption¹ and raise it to a random number (and this exponent isn’t even considered large for cryptography):

65537¹⁵⁴⁵¹

The result is more than 74,000 digits long!

bc <<< 65537^15451

34182049150723957875465592527997715909292967051739754938690558613047\
34593722995403148659339161722507712790878754551494532872308330982704\
69495520665658430384809938588898945881698360030787195207538772209924\
54540464801938843765662470558564696254945206619771843638185692618529\
59478172434208079763919030203625670099500190007799644385710218673657\
02879352905961567391248030214904289497690549384151353365747688638257\
06982312681152386199001988230656410368317185213085441672206017188574\
48739528479732797665300383760325817821214192716672847365032606905168\
19875574700683401608807310716977304425115528185639367826726871470735\
94118644833030763194113157030096241127061942397521398624377196688771\
36603409916694385788389512266530333055214376888977334094369984769663\
43191215037469056400354116918130240391274565890076671145236941265406\
93787233325071482622971067543285540081335040498929277784198584286138\
32491804419124136290406315407262222870778252290229434994911682053099\
81252641873521782615755226876154659644487478134892253478695310727900\
30062378783572678857157490616852540881237866353940854805453556406518\
27892648934719104438189064978741046887416746826721240376853179810555\
53069809718699436055101380876926215951219049347033324412128164357943\
57352802839436979460432708418015113461868782962075318848520188603966\
74508668481606352945974388811441568122300618798354111272310014505445\
45855601920483791188471822532145646789103672237746898181082954241839\
55245801724370542925833811988190403636446642757175445623997662315938\
36132483769873282947205462688474081748326706499112732650051134604934\
75886586293663720883904751455708384890336088526281236433202422564424\
58321348032894830031829817166230546130091295167220373810665987833735\
29686589170713023445122105170755644940115417370042155546740656917177\
43772616831078636639414271302090809206683359224530046156574557457098\
03480907653298897787961914572696898104038950414825988287448505048592\
05144262910595163720773312982518742169389816360739828762848649952698\
64100672670145860396668179035866834521615662700585541515649808568394\
64247851152057656246817363760607554283640163551747485235623250368893\
59363668121179466076984018601298788756731999401133741199165543508622\
79708494742452791709523044792333626881924753532595835228644924685488\
72193991943894104751743263731229820556224879150787855663360179149000\
32884524053659243398030586157621360367296657526644837027439207355479\
83289140434933567244069980510402087693018842718257511248154794038144\
78391236392330040642985155539780297565847468325190848135255012426914\
50366142434712244246013219678764890742344197828954260080246160475962\
60648048122044421993438783441130360868023021677431466661517835513337\
43081608226745324134711831713743953696094809499784135842358771187768\
06215624015517693257903007860539604917488846869862382354872712398873\
37349902941133365262608240726545894182035805776041565550265889913623\
69946653726463042509536950280014691673096489058621727832355849119874\
03992604676987699141617731785997792944524637148064473260282341488109\
27115764188746636740851415181439013291359702531306518017707457529199\
05566885210459474636909084922283157370478247089238226975682693966650\
06147709477827845772094951056381773092614006352208745398145478770209\
96170460068868382819270175793723008955559460146800547537082832825493\
99625416887203018517357980700332348608070879574311115280067442197236\
57947076947358929601070074756428178297491147216359172645328532270364\
07701793274203075141458771221185434015470515479319772651784042833067\
40328585213941515324150175759173021012217539944775353783678691208625\
45571071250104084459947563509283404647380593783271675344526292126190\
20892978662957357305795564025819114637987486848364572748373159397481\
67983790375765514260964273428565162713527722931663764636862559006733\
18441223843455953369116616505454742297253792495629557830809212291708\
92776786244578805219453034513652429144584301419328709361587650084516\
85217271882306376593194527709047125470945577570641106244394861100444\
46699505251210230966092549870883478014458407740198186556898302634068\
17347851941038344723477630314883752463184314136144842940691397834831\
96210904867916108549572261635912824827117366179287084164963039909610\
30312381005773278523624132891721089803025594397585379215622009137837\
55853287257766368108414253348939728656191453040873676286460524549107\
56569098231189257510652155357880994569396472419433792439872506195821\
34846783115223689102172446567333098868955619171926478873140327260214\
86782595843011752237992694850681200425992552313399578651785343158027\
57026503127509861625333377332329793682188694638293353348770978710930\
74044940536406340565602472334813002603691735199722087966808806649380\
99422838016465612426804472669013656105644850894712405932598624527508\
08359878555463754730249738232316945718465325636584265550131819136118\
41310584405384439005813734051618526129860119973876141025189566214644\
52228564223771898298074603169446259130900063066422874367914547971340\
73801512396087882566104765115094769272965145753873383446688067693993\
28754921824545466457520429031050518257098332323875204848020758348378\
20577167152862649411601574351315230578680410553330816258405372129742\
00598298500014291866585118367636171826310568468507461033966690011348\
05713249053794082429493656231835015102215065585912978101065376696950\
10626078218835603408472679685091912731656968046219979343765159660075\
45415535934664111980966806907314488613781077527972958935042739236292\
78579476439510404121508732558705698597241382670572458599595920970849\
20581160030603288933684320848985573924544145621889904594947597375095\
33925048931314251374141699402210115883472156576693320208903826415172\
66541411066097911686705324936634159920544556249272273123821554841242\
03120679586016475291717930627473393049703577237735172768900074231354\
70561877563935766044825295555599785788153236598676149801965618760779\
76351216489792996167652558515497283076491374818180637688244510534332\
10458056123006930614235568319397972707986870021815844516666018824874\
23598873183527230006673808067525168021848312074736571931827804979813\
01581668243770529983378334688977885111411209396488070202879824584953\
80548337204510015557240338153696654430730355068772378951156114924159\
30031430362516158229495588913114873886377433369250381741844606805090\
85775628142050569277076463954141928489016197039398196434550049425359\
84258463227242027515803207951530628459189669531330800906754854773087\
58983664933859765026526964954658812890928171992227245536837839999646\
84330289750198570585843076270608761914103577905713062516137739022472\
16579130177965140305067468588711553079650991330151145095970828869290\
44440625194668469267773021754684349916736311635439660285363298427400\
77708933801858984299785402020995857682542822824391073973951375418769\
60353950597570301298866118794663441275260796611069401577557022446880\
33174473476947011810033064171608052382982030069327933547194099202828\
68186554987174120101557965751381243319394660359954322575422847900570\
15974517607750456866661988911332392045602992993693283817053366708764\
99732612514103578789667080338624037936171161637217335807215907756701\
23673979719752467333169561999626691906409810080646922953871834903403\
91367513435873060199172834357463170521776453618319335491043959634255\
56339158242576926290554252854740874445036596516025881955655006583111\
74984816667177344089832892273859566229062196655019823158731581411223\
06213247355402252599496335440936716470104267728191504329182023036254\
32789325733877499968439349628933663359543605816951458764339987365188\
98352984048534486979875696946419386128071414036087201207433569280428\
81690446442200082079554231864968874496147213690097198194456975437335\
10617914831720236932458466997557071296271464054697532888922837332357\
21804068102190040278040361506346162896979372922815415223357494843765\
65413386214283525697188767487963050894612749190085532854919411992224\
30862280862996415466860955096887799988135141549022084779153972104031\
80866244940919994442381652396052026761553557857248488051128388392664\
56677606501863504410411052302548209446829869568278573321564648692909\
14181431489692134969518459075395094318394393233547245982152507540486\
91920774187250802073370190581059256107842581660883624965856311250916\
93518554760262575265891603328945898884480872641089949884602272932305\
61044089502923157754752700135626660872047071090432788245083093603361\
02592726988503418321721628904144812991932523941086591502572335040179\
55590471071029676160965856982497843416936491372279233127201324546518\
66279670221181316659112432254819170381814366390754615847240991648427\
64758442661619828316405162221994038733706755021114881835360458013215\
32635262312117495506409684030818642041184246764724729592972500305745\
05017946926292411541286196112618645525038029911657949570827649685452\
13021179299298195698461812494905197676300026072476795431507759893814\
96656917667523624856302961795930154911891228396083107577800416536577\
89173873578576366368167459691960639195550123657223516969726980715790\
77504258960524770408595293650722307914886071222176192427418181668754\
88127419358554340269112775579159478151649793189104378983294026086686\
86649775280618810430808805831642700873253716073644841258448272073782\
85707142248254800884653563696984971684679033133957301356385365929861\
20297611041905043500852488954989103936029172409412654623382595421774\
50777413793310324324843031569648736193040668355311606861831656295352\
00797831872321412709756558511232037034896784288941329471667231564954\
11425652090487426345699729135573431669304806547195014528004234310430\
55667737724831604922917353808087259554360729643282172555217706753266\
16603201969039954014898421055037855463090986955805796986106688131974\
21617023056655986559945704479238207830079774673326947192884438049105\
26420221817949958996267092825223669789912855266365987966786275626044\
77594647131429526710814020160491104686643652914607476995841762341080\
91376345054234219461499150201904387299458224759849094718447153363680\
11828822893347669997802416207651313067328683448633787994257191412651\
22777644318260759586804312142119271892259689943576110626975404190432\
27634174970504181642138198321244635697790287600829553787034150030532\
57478337037247265602817893429181806721240242744188741247302930120065\
45842937545999016116475561199534262170121563113659180943083565389915\
65959033352942787629415509657076879874020509725414491072965075714188\
28846016617781109408158255548066194648820724750178062801433619601253\
10822448938797784823620215252216210411773442441355924497859892960255\
37356843752623335997167972949272664229800226406892621411564561120854\
62146874584790794133529074676590228257415983041008918903684063956105\
20861119395764734650860369134722748473398219674839818689679967543255\
95547087069738793739244042798063760868967587281165925500208278263202\
16760808485435821443059446745545953337252998262627042789367141756304\
24575638290341215752510801552400739044210851226165624811427144123588\
91099844056649310631875757930022982953883400934372808247933100392416\
24021395941784858767595523963682981400643452933542560951632621764001\
39440628164702260002204395783042104483381111528445578738499036500805\
14558942664938153721188539639273256722184896596739690974295444698771\
59675540619818444782852504977033651574197479743468488394387770169292\
14680675777832866372728304319217272583849437756726235155597755258029\
20294196132008068093872725625852291850655764692814646573811211468268\
35128122946331988946764662718340824552718537833690496646732133890307\
18907433882971552156117234922601850743836847799721091163773052479637\
55524997949070471770548499663556750140258336723154044818658297949278\
77132017870181656705634848593020194253874128269428883385593706681156\
91879625070329763347255879890677227736741807937341602541683853482419\
35106933015939687406185521856898928121210684158951759809726805230193\
88058002616746119154295860258746149347636289287582515843092393522341\
91234787015161646589869361243515568878308278834821264537826584206120\
63650173039768084118856826387523641332158903458036303242555758410771\
76250681988049967519862937424993921392832848279772076384395014314916\
38770457636308307148573277281180539256045150779930886283968794818474\
02517713869170907322073594463205823652438689162382231170141742626850\
82629976625236907175791293254414337098668357964035645111766111383014\
12487960041583493386171676319913047357683903035240312291737066061165\
56871264916109870697105053293729873114693037290651595435136208582565\
14643616629655705080786596459170045204799541907661515642072240505072\
11184420421699249367151103912608434509184439030930076149753956586872\
56453899912149317693135086276725121519904124366831183087258379040767\
64688838403016989596152630008209942522242701139041660687775470528767\
56471668050914245834932825810362575341500552514460822332297841025116\
94239295130284601960728068547388930907385661534588915230238454687199\
51677727002106722389046805712478599270089103660722788450906927727528\
01246471687328905183079178539146604627743607096829669355360342585887\
91260166970327980849619812329383897695112439030234227747943757933535\
14506866881776098276594933460402143811687341625199659887053673341533\
18906804731322611113618023496987137931210383776737253399977786005552\
92018925739923796516142316087971814805526900871886504491729348761884\
61056381031614260825983288537739697936946872848879291769543903846140\
20185052461893704128109391369358356532684181637414896008288957487570\
80542765100897534347114258468900946226469556199420013651604865238236\
74280633395582143470541286699872835239811434244915587762711822535184\
38462901082826265400410456229585342127787772323156408442276874451082\
76518304598150919814844488218797999701687901859414354615793415869982\
63843263736634411494904812081538825059040632845811125028876098719338\
77660390119037297609026146435533397941400250704462425644252746634198\
89800313536183195168720375195219327265574030925522789529378805169247\
53623324906466915574608730603933053099486603782733879251778216115118\
11632743245426015142904960080677221616056005249912596299881634517929\
31538703789302749785811355088857299729417023679235883935303808512942\
60617286652385286788761682057598171159313536361302512724789143506274\
79249442207282329247466268957408400411642363869897860472531319707103\
58358317396513269161713174747896214932122218130111100003342109111667\
10823691489731645844852706645267335155432355751083807679674130944660\
39815831276125494586941750183094144403959750972168851762719636888934\
02692487502778308753768261640085375407548473100221750641538802920103\
68475971545547757516127222042591900371439999785765380320157688202022\
09722070074294499849981941064569653006595538917831617491429217058012\
60332775666432216278566478471300381497277182576776411314075241736570\
40993263429984045901656554703442813360332396849151471632631910916593\
90203683835051125705227084965974465545799169563674987701591266039109\
38499679321291749042989933975105061988404670603841082178053227437549\
19594097592338575689845361298786239931321674023727316770699592003846\
17430452426656744777501158607516538698530187837020121409829831657396\
82172558315757825928690240817818412603645268704187439303243549011767\
93859131491712218060241685913411266431001820236910654527708402129798\
34184522889199826292110175680829103934926492854889300069392856974536\
40896331144813853154112323083536587565236477547346760651620758367868\
51537101869625020546595097272705204756293602987230058521617713931793\
88831209112424734174099838193699267696886993616902004594642299853335\
00445765276487893280171053120286380690225180392547647789267231220849\
83452253499324438543206419628890693521795805368881609722972252773744\
28233932434209681576807767267356890734678981903773246942947327253958\
78567802425959906535410777678344771472361783330010534891576299474274\
88601139471774218990255135009752760586976356850271744773417917574065\
96572743949254884958301659783346937827612332518664598118207572172027\
62557511710250801142611761583366490316021554219333795496026411561362\
32209731241784050726959350311067121495174726139018115099714126470623\
83375736956223521419189296434044026362221989604475510248630125626254\
43120030217534996829966958220240623756360413780554853947034754866831\
78269129917068829885590212245630689995143007414374863948131022341363\
36862129241020811989343972569915137632543850058765480064686131191008\
63378837453026459445326104767337124140794133827802123198968516515678\
99625161820282504902275600676675936047205021495402852631544590126752\
23643918258982910633443227706817439615891934483372263604100593933372\
47937633185247689735216490565063162842873447669856375417859920025948\
86174457454120195063204508935524359553827358773580060453288227166344\
75269248422338479455722696117627931445585763920244338647780087261486\
90374173302867795954817919287166636123457715679058406748774383117480\
49020625427212800291139441673771797529873191875912161900323840980375\
58788868503252787022027122061136156319068962261873797485415847026850\
53779294041691123812652110788925882191248549180336885274164711120610\
08179461232455475118778954125965742547851238378371840204081410509201\
13518369050013444592482990428519177356080780826272755600555785667855\
05182877243716754580612898940764092730077777367235223638655294903764\
38237458145331631098702262022306631958221940244590842601086791195853\
53238897709934038376411887480548080019768981786139038196117616812593\
02753511961407624907359763876329260212335965097611278701571741610677\
37169002709076701946811431035995294139026018115582278540801651372212\
95182793279036436343290056178805697764010199345733448648193698834115\
03288247135799903495390023446413622815378807450853578488581047581631\
87512187120493425383007229176007086939558751591756568565380650159892\
63292726886684492975810224521879472036247550078330755918665559830224\
89792675053746958826663469655227581754156807667040371216431773662066\
31908575685868960203428281072060169085062769600143663063526643475665\
79714210762138718523743608252010180843233013344836098244648692813474\
17799340035660777411059137184636734651228477514628507295285751497934\
98977363621442931904682029661299978734586516626722250853270155735194\
49637491757457342394208254571006596996978185755746961852978357142128\
16861378723921795661591165226803642355485222914212704279470170093405\
63763975989123648772758418876074363106164101868633877866222738444222\
49952118711715239951992361360391762697868776166048109031642935007891\
13361312807440929108519383870191952961089195500183123312422688447487\
17617032902031929650689345542296907137964945682394822084154952751304\
87943849087560945821174852609610476184195026434603264970048313739355\
23326319813720846433927065995725619490060297201540394683036671668902\
82983165929360933495473331722674937952109572339849597430573219386013\
17597678504590917448840730351361017981522964111026663302106376913180\
82965363838013353870500113704238571296192190598378726871490224463274\
57985372557950809408674877498366182024806256606843522069539706522556\
79844261294704948697694415341776382208821703170143291411748852780147\
34430043988721126017511330780847534182997702356634746797239762222439\
51364796713325145254325780860677778153929849536803098548818366711648\
11748259616292285205637601189014680147228604457607441314577393139154\
84988574865116771348142034310094082531396180744248637237296690011097\
34748534271834417058050289271415279852049775991241294247405523166291\
79994165161630830634931111759637125770253567037583484374610282019381\
12683908508149959941020464337842138738002314180545255064332636623547\
77852034701548602523493835095533063977720569030960896083032169139200\
10050607304521977384896743183969100636238127928637522280107406603490\
99420859633424435451563007272176035710481843941708533686317193331766\
63906342742376155096162582594656220402988052296529751671869701819957\
17216488128192384495960120113989710968113876204113733558439377913203\
22175052303570127426639006744859869832445770400793255333254282348775\
23668729164129866493304425976631705495066136264587066377986650894284\
72939011382484978553265956947394021162658806845657448252970973450178\
04556958347253522416221979324219981887256677753746995047708887768071\
38308086766321039624145608849691775319771617293348174230360066160838\
04692031269190636939349831043800566881204327133453855036306135912699\
13163119942505635420563593054468486863156022899830066448228809934688\
26939650338403344843299734612618787308675583276576422651336359903303\
73293223373688417810677546042292707304120412153570919184221505481192\
02710353079197514057500628147035435059183667085995176046368971217522\
13507337105394754885637556635688743349916402219106558621947878127542\
58912055022627998602678140598983114738768808273302575479483533879398\
63491366418836978863368904825489027437553113316234414136059869552200\
01082726319165089996220213608007577676339212662736706791549027822515\
23943419247324991880724227692556454579217580552797211862349559481236\
09510950678667160678750733551686446361509766630536059711149984345399\
64924649345091804576866933710643849219574267778770129727456637810393\
66220498759089106308327801281615783466850121728828804700396007955607\
21379108544287239844142382446481370712238458486585377971980116108710\
60293883518795980217594014121158675507215265727221325405765018791206\
40114986117533271763498715634526567536693454021468905651024254263572\
76190997232330277179721780106629940483095579218091900042211052049983\
14493033275177056182299098315323484805097969523427540860895102748854\
52150392435646400616175061701823684051974548879917324134831022376564\
96519458050199430630924391485077064428929476579425908266071712946988\
54174401413543266312701392209211096299114039166692902547627087219123\
88429105808382169837074266764709232326693966569193438623300433159357\
77815530588172375914087840288601576370137573063194447121398002895191\
51717878510351885134386061428051550106472334405002702410581968054059\
56044244724340291476018389893282277124251625471918239900390306137233\
35222542642176783514948786835058619396653409293033952979866675570956\
76835348595910140860877615078863277487569254935962242472872446898195\
12172147309669364055434161518460218141826920002660515603049321619123\
78795418076050722205217557896138465885030927745739328064257812260853\
55669770455406986255248234107073654417303453733630003364978180031345\
51831906421269573428923103507364026233761693206416308471760715645879\
43433406199006370419351551188710881518689329516073682947948145207167\
61328332746958237616166295024759180521405846719365766103346500297351\
17441915489850010101098217786855012258185704269641553661329395271911\
23786914166551847896270418468188074871695618372622819022847236517979\
39078033136850512674138868263281605473071310283235874420701031447543\
10276715970569962530307017009217798684074590957276472353502440651432\
21920493107575718521808454030732862961128227187584547602663959585313\
02896082943909326161205765507880230813494103797962341945107747149379\
68667775065162659928937820470050778116248701580482546759247383022620\
77621491177661247843603907276393545725699473180876071199744337300477\
26983215229790183485846224244443767967513184476876319246817201943687\
79206258965417709569600393402086348652704546263170844362745194623444\
13704687209713699701556979682585707116857507665195733543493291905403\
37045050555568908737607436045326948056597894780645686003906599500405\
19927589800495861766909633515843898330643375930462637728281393195250\
27951391347278215788825008117245919463058459946121576746655154191704\
83622209156162948831795026906657569547591774519101121976720411413849\
88776463728591152420385905234559450707898490670440278558484778338376\
73703829963881613625587653244619837140256088583473658182237235060037\
32889722797444631179373163207709388635896740840276265375594941419707\
34556118533231020609954808714390629266430879312141980621510082577939\
63838191176767895378678015521111322662645627694687876883705236228185\
28205553910342666239205776460752090661517027078944863072961969152558\
13354897268350162000057673114668666102041220156963952467524520893093\
52336843576257194217415856880263916073715197444361411779801477085434\
48840883318004208089631523985062823070850453326948503137671209000293\
29248078560127981987603018462332169440004175702020542440679528673846\
18794222332302851755736294340711124959055309333205765770931856376100\
01667008861204881145052346999220178823348979512029452419170589148952\
56240719782884932109648185370747360158301559696451856635623873459374\
88526200231635904438796479935905497798491357453972631129852698517067\
78186253525314758719519810270982654998380224720039404535302158315775\
99505871818778975876440951787717697621893788740643730799561375521701\
20749758735541659496780286279761125717663758926811264437244743681086\
94551627357608267857642279988809273969922877395473300571954117657505\
43622727439013433108683975161347709328594757533199947822759654652425\
99482452414540487004160525502506255616289003242312480842944474727986\
75313162622204586884038974906429943707397598632113418994104506481830\
50754566218833313413165340723914785142480697315867579366408082986138\
56028063124026413697320812732768112258313889520489598602857731225411\
32525793071961979793074831829353043256366590794034534197198016143609\
79372596787112036314812057604937194898111623852993773889435790850057\
51665294433521302029610784480445947014816198378709951594796874988282\
16211906855849459450748629729023424058736996425639976128079470794847\
21736138029701208203130638142221022466627737672752834590810252880154\
66510172646524581508345770960212623899001733666220800964800665832524\
81197094779212620798781066080024857018455501602873300415874487116152\
50186760592636723208349392942453908272837941290013279096420421567777\
07486424865993473557485080074754685743478339069499597608515483113959\
29662224490856769156913719263778712271822598161808928624360457219996\
73524579126075049113462780754210027435213713642188622744343310014615\
06716978205341071630586236430029075761911215939096108545778606361921\
81191418349733474951359225696201278753566998258120405699880835760728\
91472375366835010642143791084185732357063004956409420853609397661048\
19474241237730190918644436256797863127521819064198350734925170456558\
13038161282520774025353153917331879876697141032200397586000821183909\
81719246181727672564084132703609852679029862546774415481818496583236\
09212791110534140715304011769774299707712270364464989553758004787683\
87890711171804272543580634754339610009826294935051898615768401279541\
28554725134870862830551298334535864105036870857206020630393922795439\
80860261696426197221381903497273701359467396332601502103728736269557\
75431484139677509275810102192831893292965701092810914945225360505037\
35531492971801211253761918050886922809580942147297471338362939565531\
76410044426348920874045979385093094543501398915530714789960595066124\
24444842480742372785910782947955635791304112373769547589944438728266\
22403998010879946136289331546511063819776237734489738941470085826217\
52969917093684134448425045002810164107868358886777320720746381526199\
89706028388320364196190314390677878041928741355284717743028693337870\
14678512627477469175601755509291179380989024782134815134120481218784\
18095122034541065704286770102961618450910313355427697943708014173106\
09020051776592500727949428929048440275565984330251574812747922300540\
10893050166330449799399263805761634920181479353388627729277868874677\
68986738203975711772796099579204438314256651700037880743778688152494\
17995897255197659354689880422324657364172664268415520110072742716691\
06024156878867253729568609704978831678352794184711320193431476740776\
19341906506754271299431337347962184147407478358217345690962348306012\
88556063056990104883703261122442038842479725058626570173290967324505\
59744324404793058305818903196099781304998958728669015475229236234106\
18254087424889078030649102744319793795491601482586854129458494918557\
15228105532225161914682897647864135538380282953553062998025465675032\
48740638088452590746080068397063649311539886880775696012712765062458\
38306643216672049507411799568212341464428335940372242711073715321302\
59679343164216511795049482511857742003787533311819845875146669382687\
40737687959349450565353587697211317669650729315774696041944450461121\
93475817526033816795810470003762362361974684370553918098370851444217\
83381534149857957121030516467580958950860889957129864868202436520584\
35749011925360693744494458848421316284980902414135387053515708416399\
40952169147893351027930277823901585301695374455489709708729802567482\
24467060339281166772872678121256976169821974584174855682938585425030\
47953096011422644985641941509041426828246514453652541046784579337080\
38476058906095826295335686483340615849441352669118173198796321187178\
08359620702419811467788399758634291183646058707522508915032282975645\
71518511453840674704516672886738001817858770180406414127731369897686\
97767843735838262444985001111555185095559295453284431872944321988769\
23251116676779017559752181973848824349519789192072978740718039982534\
07848376187240450090903100078714108132038001769945242491195875720878\
10542324678980519234779482626810626603192727915721702400726518928222\
64183147350521041300875526778821720044225919725587224551015641870206\
56138822213573245410226633390963093160775129255319654183030807271464\
88357726116948815734577774892083840601013237425110617930793251947504\
99253797078412699557405581287412168734996499722799156390917156650485\
85032464857326937480587103620365379770825261803912123684437188138603\
01395928212277244870795207062486838543530700903297914816284131396249\
53828255321048318692548480311935847805550417210099817804363655315373\
68513074162418453818434015535220645427369284444341964768479795691132\
22685112710706324560830147638839452981843138075689456856061244772275\
46083151612323305429979752071834737660976930170695898674548281753160\
77504228409587539057107850660392359623135291472512979064205819348842\
70846763099444222981611590768130713764306358573723203895651492372130\
67897959132877174522504364519305046773320613409145750556147854484786\
79221443532946258526130458382569950783705013840218239463274802589043\
32047366133907275889736869058265407191681761897728453547263633426726\
93722840808838759090662400629125210288367181410892504802422928730071\
55607112790165447779527757589159053777178067501163395825255522408298\
47839621025106809675356033035166392167954565259961218427457044624808\
60589560049344195034132762529834658968696812289611284818674397951110\
14864897803036573814428547945451192599852038360030904103610391217808\
74941777505396938405543934580002542986191794590736646180900788238591\
81715348739684236456090985413777212475006681158462966034147968949583\
95907686851964153675749456758254113455144962648258709956588907619253\
86243288860316218591032346035926685756022165583499011720631405244017\
28597896906450233536112601366735995088501614794538513923196042511544\
19987740253420399827538075532751979645782746419291604410805672407669\
75811463760688442349876030943825232988525052460193985265330229887862\
06968485749549198449369446387108606684263825373770833793395543555423\
97943353104477556258175566935246656297536271730198657305159384757722\
00920277138689640956485084415470341244516758593822518366021357980513\
89960438318951008032554890902588345523258568852386469081152239116384\
93837411531167768293895163058463581855308718902581943043909493721963\
15936055171088290674357016933830347229924418903787862756017045645129\
81458348618953300131168657129015574441159960117890229414592773474815\
29024223146451289749063167774796595301173178032395923506808012718446\
80173561578938506728613354312789341175940298335665412567927177218031\
32584847701131483573429024837778241415943674163122555617994964412112\
39408094282986342288788939120899502511083373953054458660049337382590\
75904335433546743910072260743011106593075722460118518836164693425743\
95618981017876993753484272061048907936699400142949904016446457704603\
44801753186232126097484000737001609059858626391460851450411836996358\
65708840259882900063142090673523684296667835095882516567033144529095\
53459904476688864668445932604723386547421955160862012776848674549586\
87345319095163036151964442210259029835827511250463845006779575021817\
70724373755320536624682310881487396951207836981166276856990720407040\
49301186317225843833276206780948006987721883489978093890091845466657\
97048246365621129262904523695322898773672533656025043410027913611594\
92970609029047226081094537006098429638915779412714163397001628978244\
81664452412678820641965715784940830580622688258396876418399971350779\
26061697682994034672483098065656905356435370993509519531973653427084\
81120917319262331742449571235832119649804478575225004226855780163636\
69944281998804066465685330355104325433472595466836723282000274359770\
47002375091835931364033352636674741732550883445936259148114683516795\
11932493131594274224327893569608507669348538658820436787403886017362\
46911654578882902285228278733452691411819710200160523025521666841595\
35377570963758016875241326495642770408884080378632461409483241767414\
20950646906340782168512534450595146581429414838807261033348283910880\
58824469221466418703729953561550949713554128338771532241659248284261\
37599424023942692103929843622859339715007626526018032042665502169993\
33482254373221723072909726541132133027803620299904753542000444428504\
02384559543391635031166020798460390916713079727511819323866764240589\
86724030439553505773924230436583900040965350693697359825781096144647\
83644319613905592880162690618507275418745794589472329737829704199922\
69101504636183474382210423849864473605218842630478113117025733115513\
35399269940355786068593825188328608049944542208239651635448666040133\
41290231479308242496748385240090764121698854350627726491317417628544\
45185268100074726198671882781531219677510318347114431783702431825973\
84523913107560183388007646258649788734224456384855578791741838619337\
21049916238698683078272305039751780678328145904051698194601578500795\
94720580578165859328588838401983388637646123365628272841971642756613\
73700750664012229059881248983565718362511767887364291550166718766572\
07134546660201293707812894054306260038739938667915832391577638258085\
93105733850090210519994507170453980923131147706777551421195644514408\
93471576509631033199380644294477776814614925798652339393448181791875\
05706726461678371072951163527391859456046183797300938090839939668483\
00221893469250238737462170104595726372148167032581875199700278493857\
62724886313373171982524513240123220751606721133359564951141281444745\
10627712031645872099537696778417610561439865005308598537924659915669\
18708314772068561930645233077090503786656918719207705278516113416891\
41270426010308295720769310572334560082312142093208879331461635677230\
51356541326391570761873346467289031517670456266915855779033677799469\
00519066055893609920701663761425717995396996825312139194066163356199\
56883951310778256855363125930123140515727846931852397148175748654874\
76671023779514512809913415223303317259084239077300563295062803297338\
37633726830615293555503351734984090243738521559632291365581076761863\
25125266136630530763072484572858100161733073234957461257417179402205\
02839939729434992989735664349002652580111178795399485864133005513154\
44440636457866212174324038390782593986765324531328905546607894358773\
79537832252580379929568120745913856039025359432022540477093243219437\
21193066391215628684694673593524268875099606451212666634790229088394\
48741315299016080531372184294241347575735750699326482883408777175232\
72552839229619196308567211140181867165865393104499794645258290959749\
81404688646607143375570300034285760483734528281148650642399819417220\
89757967061396645436536438867165767119487251969680437724293141711886\
12711625887000805648280448506442595890072030852071005557053054170340\
17867884178177422201835679034365966897182215553650202320539110964948\
22639504212630346895455462370631034219560108109442478202259615765810\
26671802024127397590889872370407867721260758610113468808238096963515\
65140964170772071462697771903721989199088946339281704854726647499248\
12213693606631512923061285027127948789624065986568183718428483846783\
25800109936565345491906193605065802058134388538743540110904679391297\
41999962673335106466137132404902744695188568826533826107801799274218\
98962779135858066288712644680580593381290483228298187587105297819028\
98705862145964418974205461838366169340260200289289123518655742214796\
54334582883388858446936949464882536266958371222181532815033306592838\
06269749058657171384041312357715378865687175607843898055066242889708\
87757342942669192818087428814400290956801003205790088518099036221704\
38179935392063188451507984438061959649439576349669589266595399808686\
13185568992643585879973547784086210347171111670461392177295242179444\
08330969873323970681416808105689952368447945255924322674684204193926\
89393856099343483081554382792067479714519458179838197790585253806293\
93491111058417501775424453555429532709754029202388709214139994805879\
45757197828434279851008008511797355139547432790751506386400630046442\
40464833701922942789691397717416460026142727705581959617824634509565\
02588362418534699516156644465986314993185336054292492330842607734703\
58244017820469820685176578187710796379338018044009703365473415559354\
94916845849251281615888622509739757123908867305504696219432640470000\
69128325688564044507609338592615639786164966421602220301116567551578\
35823205492073602438420810474396286241235565658966158245181691360869\
88173276977813510731350256056931755766561477578780954375758506307002\
92768208599435063446782610450254971655399818278992801538186802572543\
05532972028137335848425884420833670744220730798288694233131180117147\
96732215529964803216082752281037155918649848490880987361901868122797\
45940661283256774241146257706989026179224995305633744655788253758863\
27518037200363587035967973850637550636817433926550173891135897234772\
32771337241034092581598820699799152589231559942177443917588019749128\
40224959944158593719892580757680293836888288093583893739132988745970\
49369467645904942237424268870241792095308384637052184163700999360132\
37630041000686623076914569957521094315375740887712493032005278521585\
91355191183635744256731513921833812620300787934807682352897293504452\
02377766793691114681079448604170529521929098809147477455153620008799\
25146743391623354328292107396003014920521663006545071047979688881011\
82987744430593678216785938816891538407132364526727634196150673017813\
11583981878813958591735493668986157135651089053737706149093714564057\
74627487214069002120540258493024886067639274725935200868559504070337\
54337589361861874620470946669387274997632786869857181598619500991190\
37133610642395926009677845811452251896300391082506471975149373951886\
35391931036279942235464489775682153071095250712149407205548907278498\
36369758785154839682420877221306105973915064163181557668903153522830\
99232324842270147588618106962618371953451168733131144454384565163802\
96800147165846592090296144385357650349318259783406896576389266179805\
02541409749648734054986982307172388443025929860232164926917959733581\
43845087848116086271504982379129988033676067884101451372689290752270\
57968536308076621892953855791152303820371476634286705850142713659771\
80315847964848385789554613011695151075584570705835693933043511386550\
16400171810403346170348852727890060309756373662304160633139942790800\
08537377351530067015508771513392662376723399452757083014910124257178\
16757866760459881769542617008422218792011996887550506773089730448130\
46459353685391204883376790523284160857248504395557528547379645036496\
40117722800524388797321183038896064511898062014183268982566095307889\
29458648646098567061673961114206938921990605256743750371538409657867\
66215371249323454496804679517790081214094365770617645274698829477953\
38832993041859081006736316297877219115058776024983126348658354664590\
88060766793520513875187058584122307493293773691349736949700982897263\
56458338535609695879971511086987954586918940355908361622625845541085\
59353778351607833101477160164075406093114516193336670744678180591549\
50218185380611518487778459203647061356085806216375922686582343989739\
11654317498806783413456437806443243141154985305633591678317078127592\
70692766753962196095461313221236655418925894163995295567866101174529\
83163606786028375032614173449655200505676695008670379079915911385549\
62564862032857321764852125908446021656252911908628230982329409639189\
37744056857155917046607281907254678638466251193856922497187930947790\
59508440409475011594474618501159288568969695387292677188800095786434\
77383536281221000310512980741477717082311841994273639349774552708045\
93115512820536995352668155024714986828485364820651669330121913380833\
32877814703415641880526681019207254247731662290255389710124566557419\
67619018499353144374943610589085398941288084764362368939266701940148\
44687566482020818511825073146186798213080550559852043907941206992873\
64696223718556990166034871781932425923748422901945168089144729436737\
23965703289791471173720488798384669980680014447168158212488229265941\
91704505625996237140388465209061226841418004756155943248510264785276\
07363579292648082761455395841542290624406274824934426027602808038365\
53107168260307917382552739498829456963984167490203141226740896297197\
75359739806023432907521526608333467315832334702200562532987759940489\
21938596195208335009258351897776370598563740154599487692374920459634\
97185692414245323388444874548307354873575359281623033173081630781992\
12465588940403163390984132539497721024093038372086985730673545731616\
26645853273048778806523361695870806802344374016526660026713566510928\
11236033838585906549324914728836807429473676902684142223184452681163\
12955914680915201562982938653240260963459714250984203552496535623463\
38610985059162645500319776951613698621467038109615191373376631977220\
39479145280111008840433322971471342197048265446223431989848543386341\
70949638160484785366052285956546940966147408934976564159743517127125\
51543348953888309671228166875698033853485707473361408642002858549621\
40217527494357894016988227365361102675346632149797022515415250543700\
62042722060990363781471822686952589214399606766634255148371809325563\
65512507724061356730869055652150118291264991261477942895373633926664\
22217046628247699505458683055326984636827309919467120766152557930211\
37892299926273423024829611144285460363362902983219215384107051406507\
96336533176552698716280025343492884436809840187662244917259364232494\
41036771651364347287729387668205173489411730297895507789711667339862\
92921595717031386352302872926000459104046680543556259354530617878693\
69995789703229907775867050063378036477579143723274200534312293530819\
06443109561709187824155406129958369130417198123120139763215941580323\
52329193394653651500129412152300212317086107609425171288759330790815\
55594602393781790912947830737885233407122033092828606641459301002987\
21810613359186229763897768295893971256950065362248705773188017277788\
86073573878959630952939763160597314145904811870065772595182423756150\
26036478252842800878135219844655424744624436244791670864354967366641\
79290169133290745799458082349963385508124553983691313342857191556630\
65555216415525972625856426893923247031950199663178125315131441007664\
98058944264568363671297314116596867510248735363250172272021838301325\
02224859679281959257572467262052012603141714884826316239544743044818\
26762523138878591797124886091757613462488516699440575112994120714361\
10231615938078397825178673589470764228959082840230070814851168944981\
74589513221324896304366931060185314245746189097423275216868184875677\
41846807594713243501384310348574080569315336043211885306076370023038\
68474839294586879728687759551170712757732038442265108298771675012609\
98164580598756776318775353595934440717177702535739116140920594583931\
52706114427035732881427396242773072139191680994069969849506826323790\
66447568673664771507109845502810001947860859933767101575542060521642\
69879742703111875904255160245316989036915454206084599409054880985878\
65450627861129300480126470418575418373880792713332980461232271291499\
09270823625268188051061687457641854115210682622315103491225125808570\
47802187895308610874206395673054828177495634051923635725965603080292\
10633805288170847052200889290768018714647282996388617284509344533881\
59050532796536595920024916539305237674145795536540847374119878715631\
98167952592955980968124911795931105127329840014471730454831409044424\
02529334301540210165252371754704075328977198031750482729296902442655\
05167892888730848884020872153763872322640774265378136655147562035296\
19509567294372765073190554776294780977382894224272679241929783601000\
90452517352856360189217506957557300966023455889679410773495646403304\
19182901826069100197944789500838998878281462421100751934331962026330\
67430379371307694649104182977929261660821807029687178123627324512943\
82923936254794834140345817443335882002771089955787215004246114674747\
35447088250139744942173355870708283810028752381229451453393208860394\
03794979409818617485036210576471358794831588994002435448820166956933\
77420267023658680126900130974288459609400733914193207950458123628730\
37727230733880905531162465419699901973689213324658241653347658498185\
49264211310891610055979832580175002439597509371817565089330618329710\
59880188314419388031319794091957232287784982850558119116767793634754\
05036606997719813619059447644304968270373566564030762688387334356891\
90775688842772631989045727646672170622708448664597653168793279821345\
02137605713921253352880791005466853402160652910545856966220779037123\
12374624376651643790375878299619369140330099966701993625698568959453\
77668532305908804360678474428278934680334201960612461928700479405730\
09714187180018389989348659431592461214811964780159270537891572560744\
24304409936855184234847839798666063726074336811125743943188002075437\
17067790052832130974038217228847152016072558528530732304899619432879\
48505417163768444504096499881168376627671589063940334681267076186203\
88038267048981073602870675157385701776268537879219979386739897431300\
90746058270973698059352046350665195429434554106540758110827212758945\
17885398967920853603981870888418925941534537939648481616999105478757\
96456117364804375797983556246863502571629834752431712241622478176440\
15659859720873306584264155270151378315575641960483299626489649460388\
15455751951576089546881956547541070168357062128350244229515330673659\
71579984868149805760417210210435929260990182165757749414783609608295\
81226511857050325317646752457534199979419278912537293600640239839136\
85357645144529109660503880940580161177757819465069540529421536747827\
47865494295244340284483289407345168827455452729417613054003386882001\
90933368676318906448600120808564401549327131941085776865463453608082\
95946083577544980413327635048823071784878981792158590318222596197833\
36756993256975287522389630411025913240165795088773372510651673966911\
15068844616491990939145762848293550346818679359246244146397512508889\
58764295566637904819339947129262284388407991319577625188879130246744\
20359194988117420681435320583007051229015522272309455948743661443553\
03020457298206360572269448940666870495254540848388833249766884497853\
09775137125454376310613108337391933003461665053246334235730345325931\
93103734405993666557182099376177180286211544658726103791513375176695\
66313029133504045029445865515296792398537129869151555182700058750056\
72928987647613945509656450319999990820127468734139236030774099662480\
07252882619905788306743755777445725687564847608476289679878194543600\
63286163503033065445858096593820060972083005465542331517943434661338\
25880082375365627242817665074960229414757916660113784489816415568624\
90574738836354519495170189082306707887345302790897678488066607307741\
96712052734509849005068942551976702466266003548260802518433507884870\
60870737400203450720555982074815806534671564389975850921524116958327\
07980152384201472079519814171590249989143156784192520786528786256673\
47220190336916066557746518796682439042461735578344063934917519432777\
88515789758015566842267702723719626725942078493725849334886642299947\
70030679468287120051262729039717871969678460059934994249474391411714\
78278008490896995322935819876793350803375852915554004211740165840964\
58980973700884900486243646094922098829698772607089905777239647767010\
28189341944069984381627954788829500808206910447964536841718625763251\
75886560221128687943749533966130359055198784552381931843249842998351\
44583050786817248493383162254969694615418250109380538361146251022506\
06401296384006416133384871139055031090707739841146158958324065062495\
02830620418321422399004694258430111804598209265532260093459532094288\
05603345924024305329898011813123546099972716996397667359610863833008\
31645340046212846393336511305414924626105766287929742523461580999754\
73606018253856458837654303254400856860363472580347281769471032284585\
48369052513310899114765447112665846694879805233280120712927163065777\
48413139497879925010315388162232443947123028694957195354494582605410\
63462487875788651730988734054006617660475561459605599980375228315431\
24524537564131863965083801827055062127771998655580552281650602555824\
11856153917894676910298758333836613331945779213054812530103373706836\
54385555713539435067285061015954092646934020249189942088000772029152\
24537359859646047540204272110420703327417866377169384652469720921324\
71224439865888287253961613024228836503763548771749063095434692077744\
23182965654650394905406975900212640428709095696828885407794645198220\
10128744522173388069891144515618685700698613469536352975852207894964\
64633176634726604735208014543005030064492365102092189549305455165180\
39290704896319481520354863038986410899970631874319911557417562070037\
04010033595752234069579291978775531721719761997732447977062169674530\
64766537931725646392782167276683648603674322330063664618113989127152\
63430105324901166966208945910872391996827827102145540739562789245744\
35289004966359073409887586441996926373406430494465011842161858793176\
53598129221445850617568698019709155369056212127091025126872437377686\
62010345232326362305485439848468003068929818208876746913562701457397\
46213000705047577010358878261531852560222079788341486932585878376481\
95316935034227426175555534243255684853140093339742891376713439221437\
61346027955376747542500529511463598287812319945463956151482458746543\
52683493298570668346095303919013272765161032321599391982645532700840\
68483304855084647228094831182111924325833534274359203473573704034206\
78755726484973414364307765840610767798153230869912446354247862204792\
74133010059138704910591904683680101791281674547437365592155176005011\
74191383359059849296661608561839669915015114387121546152884448633032\
69020677573286742027305838963364096189652561990851786191745618181887\
63189009692479603828759832370301135236572737887983067915401784834614\
30936774609681944912871350586902281195459114757170116737649582260086\
72030360200951519582431623531916401863363431053125730846149928541912\
47664100712944702889402417034434290006279085504095775929419006149633\
63339135805938487302900395023261338546968005808602865359698904087169\
00875725475113991376066084590456483326905747081538094226256402528473\
15435257200183038805653016292263978867754585196720256542483442991056\
66466902738997087989919314496049615444982488743463582907753411873713\
45144086010643847713706900764580699909664370205300506864564210058945\
35251334861042350797380249524131856514685634100519628063628139332018\
07974989624813148456039235765710904668331099189134893473028468866909\
77146037958840683532213712143433463947713294737159285160933919048706\
08947587806418059723961386832404821845919982122291828385356406812444\
15210236282868789029978405161828416915090131988696062641163839028361\
80632377080666067477928811093937227105254674309443875213419556862159\
38668620270360204433195995506694136777939210507909155718990430197994\
43977365792066079472779802042021124883814953590182590774342147964456\
92503526377460176411536433832944039036686117571587253006742679136208\
90457427824842319098211497326072259260241712543814133407470530671464\
74720226894711289256934081190289884393270429218011022780561886306599\
46496941828759001039285509414430327709471033639005177526104538372596\
39242818951241554509995995347200307510892209924299469675814573650816\
22346607174423765479393147695339066402237387272804207464629731716244\
06927105386658974737589773224527604236729809651088716843090247625797\
32638239896178984667829151850811992283017801341327016792287221943506\
04949391493655904757510489432151312712685809239347273621085782811909\
40513578927312829185174005232394446615793433535633878734492933402481\
22694209986323418703006572491409310346053061408023639815249053115728\
74734056701822197142653724824344343057760622141342508264239679629583\
21849838243819403906720652122249909280313224274306888240007232333981\
11133745526652499801755408458599600153820677994745431457123452615052\
62699314454712079636596418315347692808754335348736117809767566088521\
11984573898004609207629999041585496887836094559924048860974459366341\
30591767936529832864283186323250974295671890529476170943408714260485\
83734278041421367975656199955291041882704742197104449519595373169608\
80201143442634269486362253838196084416575193023228750573981650736829\
47276136671578204267262562307104253134899383921997261551089380804076\
14185562305899056376747556259978773094036586849520228919818075291293\
19330811476714230715467619538652132604323168779004970366847568716625\
50352610002725165707195763553408451848550789690086695192715145569426\
79016561996356042443922372490976265653186488526802362995811122602587\
79973599066763513055127846641395609200674076671304219386344059772561\
07764359683080636811389413145202166419673706441932514679080496409097\
45761777976211401415971393470264445513638414592870487899968382588669\
21262964828112558450097881006521786963402293516021429442921349218430\
82153739044469757461823763514811329753227697159313580007692755796287\
04245010666525195931323357634323142506389600495878548972911537119065\
69706055668883444120945244062432889015677706172206993302413261601709\
27111635723993867995650062541385740695559659064380490168576090505432\
79422638792618715418496874990792314325306697294464867232549657326275\
86196012901557771641160492247912407094302071148504071834685333596259\
44290129895544200695001804712654418830358285615083777827679188812793\
27757905208057843206058831645061648912174967511105356710437674044432\
00144826011339930920419520744684205867858745785383702286731111489897\
21714858585280774939387054378912210863742934573628211640003759482803\
00465475059788542400561813182353465215314514864252998226672328290106\
69087652351297894577524471188473831276467715237795322834668956778423\
69369920694645516431635258442491273645684146941832510459596744803904\
21969936764154029957057877193853096946324564112572377834709748766010\
39296539203885164607930181598026394977263551550128945501631588150624\
73884295007951969540385123441636636296359392576835370494542185770704\
96428083741811157071484408901124751608049169310396855812855000026845\
93067391357317226207689806198576439509398577644979157838580898170859\
55671186695359783629161573354141025878978043588820600607312065810951\
77259062769889578340530386710742497497259235751935523845586948533106\
05309953424566358631767978759406755414766772322424724120374965858237\
13805574325165232398329646236435748069435380752191512632337380695244\
86368145134251020375433068875119066645028599008877873515799687300810\
38292135246041515334140132518913022464645020112236246371704518817384\
50263928826075641375631871343776290092473085310812580831886248310543\
31241915267078476827290171564099613754956123414765300472437545219060\
73682406544008993012399378497731404768984926337129776515381796814838\
63261555514746881927816239735590717397487135452476135457336380037423\
60911092244913178673831964433534747136892081883236014902762835816804\
37978997531598419253868700740734199129166717870149750439365635561531\
40290474595690594146610181551803944594236066890956263285187378221519\
14101095742466917046740928578577667995756715528032792873405279446693\
97396611926637717096505111293480325163031238735387227136461896746783\
51806994108714167682822984838315640120070423379339650393041435957381\
81494430483222351072083087648944890542442753025870997946182476309772\
72175793412673448044093949326943665436966499862347028404084017115399\
18921108126605764403546384675655254946991399631450793107025057763311\
21440849789598556587676716466196152927878146604491024750029854777808\
19275222024907692994943360900237267255677551501353219377440049640820\
79252080916012709301717732264771342238814753234774617798847066989178\
06748768245839074726243483937991907833629183513636477619778424127722\
81475500074427394942652163464579987377892295397668952934431453224938\
52114336570451717160571005701547096610111123055039570818881436437598\
51837110000577417109549561492336521276932541228915561276189976813771\
41068315208665692138723139719457655376924417978389874453074145792409\
48298991325265800866748370586498193331143940440481434150468066452767\
27577893910460312627249347495744678156455772919153412084433924889168\
58110590025482837924528318491634254567504574848451854558952658041715\
91928432607055862004076873515528361533409036296982292415484889651798\
35733470726882046809887713452905089205314212826908295035000799986878\
11410477639222358986185149129041469164355785052062067194067428641675\
70291008520017486272926333741446851794555836376424504723265498519409\
85718111278928275749351610698765943368495595080503896678905553061585\
11210780816539822911680548457740353831585473143691029142123822032373\
09923557946079793283747221518608468508514252578799158651767654051904\
14465366016222693395455657478671854609365623938245685066025869202077\
81118972398288461328894471245504588541348351626032711905120529068338\
72033159140941564436061574362160831970828316905759197166209001112458\
79238711550818341047843163748963708162889972678450380466393607177974\
37132243878857248850861682784453307480051358252535782433306020767193\
59073461485076604650404465532607980921310657026470654488059430872905\
38334871015988087990795062756028213310898497571784848357177996351420\
60921575035335093649726694609424995550898119170431417088129016322195\
72616616581467642210156698508197888528249819873738930209233300220415\
64210942164958325906487717625950580785612541790059012769199153097854\
65503905249926706685136286575235498828554332807829834049023112509298\
76816519617406537058105800500008439122913260837925764508487322508726\
13663779319392844021774618951614638089441484842298528393746228985211\
25599169138902292280461215332399010402406331516036346396383372788388\
01709410705702615904906493035157584508836832525577911208074273021207\
63803710835596438944469147066438413397171714201875204105049912948536\
75856657039698439451579888346297065435556464676918846367782782892661\
22320786787988397200573338349176521735336573982466168902888041866322\
95207836288322908947494322394892951589710599506105176388370707991305\
53019366622722670570577581488331377458281356498842827718272550371799\
90781641058398768066879357438562098337860278586801882842994736523684\
99137864328838841623721476437479748326395056434962209270451714810743\
49483369566423761857662406005156278943750846413721577203497844143077\
20991409712694200325011419832000035762217584621781009697162196167221\
51334971482957152166469122168529146846256732033151871353520163321541\
92187108131740377590294067172715668448292388927590154400633921607101\
21551971057868736695911242827136688430092425145980142597734180561712\
20255300188106819616077779609967522134593793365736596653859300201991\
51996227838633536090789107078185122922680630735173317981692699358753\
80913865492657434989846578822073239359674999003673965564061709733563\
25897075587446867043483933113884898202662189670087432716498139598205\
45886497751475256057498060905080129633633379449401040285222672165223\
75551624255371101998948212413518758785531132975586203603005454440530\
21303198572434683743976889593610150264476075503030630369626828025686\
24016180114830459893688123399849738916731166866031746166878443388485\
00371594207540454263963208716496781908981052280586804222280556686090\
81110144184446419910302731253311729634881886531606091290821814763187\
39103748870438252999997085762658915720176173478251478195594453276301\
60418151540083033390534914038897518802397854335643623455116113738194\
58273712639249145523128528480528205706257705932504088240472661496409\
53845719973913648719692420749570623292377724971727735177231881753154\
22420265434357931838909604235215707486529961815871128342599203714129\
53481450991094662825815787810930197913398605280715438821229059677440\
72748457897134153238806337455039954269093048216374025212569197667186\
38824393724621502653112066456523394587372605811686111993704283306051\
63424913215367770482336126668887012264518555160566170203492133332323\
44517717795130624515911830924800838519907910099462791520337334383712\
23975691471562701925600184678888343102317559483707719658221246902063\
66035813305544810467709303012164462159606585638580366172848812592761\
17801458900605579867592195948123794585886468183552634659931723347429\
45273698331158380047855372988396852428327693660368114763683535274030\
21856694944754352301139600790837422760918710232657239029668648790911\
43017474055705565379345395577557923475206542816163738835163039160588\
13861590619897318816048572795138772752870548498208079463887313369777\
02556011176343549594492069193801073965208149559103091169436959808022\
09245164705277597631406321350914522120374006734452898148421031379024\
77950399491170770718192172456823857513465345866300603373905926270921\
86145975340788004549023198044322973234659023137761214891428468735267\
77693512836310341417717041793829552969636267012503043578397025173956\
43897822616533185443171457765035146469119495144892465160484852473381\
95373738131475920046885701131111885161124646416332865814888953189337\
03950531348471598470380102569084892188936803778666938195519108757310\
80983397214178106014613233145023524876249935915009163316849107767082\
47920457999344860299414100361654068761383021350076888688174374304539\
89258447825777841436608922760614029588391597599518446766486451408266\
96164309579412453182721057851386185507870752052996035890075577697097\
08694354225069274587175123873585967269335775050373982808012891037094\
71760538113985418499057000368900232934691277908043473994626331191653\
77159096915273884646075721552029187928991473756442761640259603076780\
23262131166078233817960093457915901693364919855336555748190667876596\
83249716468134003023909789059318500059617364991255751735988809177271\
93537844951586319168329074698264318995398568147834610289940477739924\
98264221501380467902515787042645286595656995163308958532044759872699\
47469710556382835405046460733849575651873637419400007891406414054768\
29917725385434373108248853247765437102226150016229666096198442928263\
55606606482341191428837960004275626891833619126697959749285404760639\
07498959269540297816769307112725214443759744293436019134256934870060\
04402380679905665948053886960320462737462131279670309436752463172850\
40252475280265147464245261531341894412123498708381566276510315345865\
27752329930592985265691246029574916925678389067306925157414399084880\
72304382745857096039269017383708648008344107674996310281578775698036\
03177168301212524587425911196547367390343089487390722924188231943259\
82409057469319586567556394890297128814656224507065085746170072501515\
38996349187991479565092992109969742934231899862192354768785653945136\
38125735724703715968608385204165549109301869685960257400108281208684\
66816932968957052350363255114614568661238903169153013289363128325034\
31797283742182888220050220654469903114689032205586541531164337335835\
06999259642617173992723613530768981212589737620473095423952002883764\
73557472799053100843891658821739522968236218921381895810750788989640\
21367871085475696921794772336826442632598374319498229131560952717572\
93000778709053832543191586383442855942150758054034257325612042621725\
17340197181814357549054137767248213417850922142031870600311930954340\
08334537527384206294828318410224794644216404781715932237233161557521\
60916273456707758913025831218426148520594961926518449010108153226434\
02503581979782448494386378454913237605408944158228947721080824307905\
68474219590889143577262038974968387397016375092333490610467399710931\
12052418803741796167958887083732460396377118978749100773586805308767\
10853586684803025140408671017019697102056959133769211872302216160099\
68514326179261663073827654352533133228058902337526633181004843752073\
17772765663692903777439642247353399883440269917889598755088977630278\
21605676810850045480583048872642540013759482752995021932893571248372\
62699355691808875614966253078445654384463004804268285428510291641287\
18557953753513007106182922019523475676872430182069999800365566560322\
83104569977255946845053608833381534339200998827369084531401728549025\
18281740849885983796867013336201641798107034759228287084372984626450\
43321111263581671858774398564343156846621946545221101692544536904387\
76665052816867048383710207149035678860058721210064557053391370041597\
19631456947631157081987088042554528114626367694729678686113718751373\
17327920827144485359748263881352533469226775198709061750172006030338\
75346124447692731383380674102282701521012848885305128740474069324986\
66834257243068917699808567496664537552745581043414042423757045717650\
19828285007523705103637459741647922999032322290519619497529760345731\
57270559326244424644756009530928298961257328249021113653868634200489\
64761096382071841888503932255103474980573697274206519652113739929565\
92337923863636090378705350786689024079543668323015228656565657078827\
36948165708154406554386829797776509124407792948204108270231450488897\
55907450295821492096216260707897699771405582843478459635336973132082\
43359686618712811434832656068881714968481591765058320301237808660016\
50964239924126065706351031417920472496672616886391656790272074286379\
10132552012372000650706329831116885980275152757856198784199505989312\
10049079900671500209628967463802099030523724283902413040244262470792\
04588311055234710076910305456263466660023862915380642564008451895627\
19207955557558798197414206034549419278509250356221483645287742207601\
22596379442581214008521211588596793183073258914089261104462938640148\
17244858487385797443091328170524979040521772754461054353395042296153\
16357143994248468016063369687261865225336588807350258949776707621501\
53457577024333836880142573016537081752104996342158456343293438980433\
29333395875891070701158695741755154594002595985611384319217767156983\
64536125493620982325068217898856163747134141531817095924783422940357\
98547603826108033579624963779390860655453937492710891466400340392795\
80619923213828509345379687295846906693517980073215981949455492530604\
28451141345328205508134950585093590401939179812826515830167233673037\
87722541333728241795926433793403683727809149015052597602780823815294\
32592514415477705132292024113507461198355059670349631542983123864375\
88650871188109221515246018818051908909469479047666120235703295420870\
37851416408456875442410034951112262237573714950033274300432961070974\
78260331177215375413912623153771375598964393749241167291416054302044\
47604044849052538558086439326251278380478334387875331896755272880887\
30203270111802777406548145257184131178066422261172748796579877771803\
92036729326559544670821412888334285520990587040594671779555531474390\
00077578877582210757225162543098357903651968850845275008386298270857\
74417448140971626612118719882361417532130632988401613141359712105436\
31850013492463334774780524116700614339521435432061970655764419612990\
68535007795795633795363477126869812707061740876790580241468575304771\
54814276769673666436202595713344677989221729976966727420207154610368\
82632484730284642692144378171542130171336809710985957898710489377884\
30192707300642040414947052567290636453198405062964316624693344243196\
24573916487214649036759380836381899745534911325426207929917885765663\
59591318183112213565327289583571542835146851454009729176375081497556\
16765706526920859277227980897462107739757262918194344216986045098297\
30628925852451100187350571135547021326682125060535198459545611916308\
77046167927981811346222353371818349264357043608643707652296760165807\
99412326928695050340648975377371934955423954813526697753929860580672\
54286138641580308426720817079871900588845628441205296921167971291303\
11825920132479691378770452026035964600654300216795703160588467249515\
27656119799404790604680345587435137248071722415203938472602236108268\
37723626520049840928136315204891736547348252521746707826274588643312\
66572290508527790080675296785816164749532509491392659843183488310137\
36567869923662335019111489288392182627564105384240238113297501005570\
65033496984911623244237673307287576392494806499499946013011213484213\
05660178080997411624058274910360058024752584813061155080255905847238\
65892507431103034483073988821602735990647461598672220007688105101191\
01112997420384311222899123630121930024437674527980270578768366847906\
99898368514034914421743360982337429582488530412093053806534904917214\
21752379179258455830983860956211930622153372167466631249616895187502\
28842810394459980038352704088394480612155590916662393937210121024709\
81085737844843564119342008684787135255941287283402322251300655905728\
99530852827209725904898209967795220965196773892536211615016908023272\
10022793431846684904588307221749222113070579233044797394399378648885\
10590749148650964064808725714945895344880957001801285527118405125480\
07412107745127577690338345804490467000600458132667616899717518454986\
10989492262565895873144138563067461205944682635295669151585146258214\
89523163802994739248968378376192093092476885206657581966886270298160\
41665869383181674580313258068233005674405095869158353050035249217957\
20357510022392851228774704537767663559582275405100113528974463817370\
05433439827148947110962675773538806697926482121680279823000883990403\
22785704726237974239247062105099473653029217081754089975587537998137\
25338042850036515660727354079486150074947674400276955021266683377314\
57110159335324908994937636335557050414325130268626903092877189226511\
90183071212354045303734261658961028319841677984545079242414664631924\
73451061579382612500438768458585716274363907099790352514219884632036\
62534982769990559135638622838628046574855809693018553747285811538190\
49176236092627702661262133038062638410603561155047694509784541351622\
60672570891556237859872995158676134234248827363749634045553320637592\
68247083611536672162312358296436136923411421313141339748089884124931\
98832110717297897827456867342731100646439903556412160468953191175051\
48160069109449420025943977625038354832890541527000871455474801949825\
84349415629617096261202636602359524959118727620670543206855473543528\
31761304778945255285571949750828710000985549624167690012319891051894\
60983936888529944189560974732324530254605362668047902777188542778764\
38215750945008425540663127646790625513145372046516704300306431922410\
17613583214764962318342863286145271326119705679260448659317975805446\
85751957483328983357054571604330781341501211261485929905337202197619\
08335629440118847652578589878123335912644325206927004138410033559003\
10255628782451092418362135187396556223628757843466952637594463455496\
07446666943369638113089962257154005920385242347106656206388491977211\
16890215238137077887217115470614911635384390416286083860272149256132\
31373290064952559841222913471553791773633659681391044447638344283324\
61192114789897405918054317137376784082707498004879235638906082072421\
18329645513107768894539024271234001331208519476475911162207872603440\
30659508556653762996813568437935121041846872767593620056700717482459\
55500499427745811580026882559399112445904336754809101832917271722991\
63606346968406218373839712895072521370715049157357645985217085105661\
79981822615731013599356280371430991664284649068723422882909424756493\
87611887398165859487488183885860070971944183382000951729831900350120\
58010043298271260006766406114223045337323105008142775626826690506066\
17339932847209465512530114705285104492621211051312158184429247651225\
29714917583857195622774740744095506131129233538820237564006647804027\
25433185688659772329382409801758343511073615679149635570126751068722\
34750839764815870454018619103116493478601532730665683028659495488608\
75698338199303417161532467970142151321662032205342003014995178047949\
59391722812365872301741178898489395481565397664693242655750272840017\
11444533321322706274220674278576473239438341098961914415485118979332\
25789244363218777695093802685280296077904264616602448431326000491647\
25629315775735335890493610615707845441575992985830482973063121209452\
38761730609149954770944900569105756823891945464001912805200419317968\
32632852233717475460276503840771545063380277571833857514096541140467\
96087827756498994725839554586688211608483405330334516228156063684808\
53073929896971233600471717617297834846022460532695433236401094393633\
03868519428508826247006209439832272241638789010593554060553205549096\
62703404212519714518075038161584969044510542645128838207398659475263\
93163946087579442564775650159800509347012129300733969911798283196927\
02738952749135143742975729368641376386557331067990637315541568254307\
24172863302201529714010049737614628881017876160399664629468659974667\
13805638863573616308045038941985131123211890002557344589040603223828\
21031191150359008832414959509273703919720554503898642778213737123543\
64756903212956761601333529968598272488656557343050499063203460614496\
92886612766383062741664346638008017510721717433922175701123934740814\
42531772818875303708145109992832225185435148817170722296376399883563\
90313829577547785285270586909368156233760253889149983371773728774565\
65366441461277091749325061306678938229397876104302119421702543641538\
21597089234318401319176337978902099049430392709210386052599459653722\
33785609037693790732744615343742798804492983844847517804759239296514\
41053200253230927611006289296866688082672077421557726893453143031284\
02795702425385930684833908976685112356389454440293816542537039500557\
06568632901116293632450301066967524415946553271690329270844146813764\
50920081904955001458630636200147812102240578752607358952968971812098\
23459827302752003597467455983887345198092069235334258701164975855137\
24095840636426580024857680023935718285434511735532621992583170949281\
89989431910439093859171827605306382126108137284406039641570236315521\
52893625809299663569935790785972066649722200106813692930587599650244\
28650152993853890283976090384810149242135184003171537640152798717255\
48574213322881920353726606477341871324298197389372506178509412986316\
12732446796463674148392733879842021641420018133113901523986115345395\
73053630279791220533159671256253090406075757561273126620133546478019\
69128369344329895756298389862521117054149512277290358219495780327057\
48313728186319519119291793489310977243037432087001051342439361351199\
29834583475963343978876562124921726890768868768844358605718546715195\
00946142043115390796839642538018181495021120796636913250103756045268\
26819620150476820479155334947039251299709202437427557625260355138752\
20000279048067301418352315724207086801574364734768454656448809503912\
67170705790715265508236267053700162012947323058757707100009906883561\
27662294098345840359955668926591864239769164759337348240356524861637\
49920493857389406224243864249180617348415231534126031946015421308147\
70459906527343565501233297993388660838045570969071619270022724038667\
36275978152005096477326049244444675220196452356228863661488108210650\
48888938551877432822064204949131971735321330427761654274014481170984\
32950787590125470624251849090108659577003394834733662124113881017708\
27920086397409223486197997238047442368283676957986526186434429871652\
60243844973908589636278220327455572315080389853193896393051882675116\
24077293260880379196950005138962940752368683552134554009227167766146\
85122546449060026211465432350135833103995315980281553405918869316484\
01016977217352925614934523764747650277032487289037965354376423027611\
40732187299064778947193985080707755266090292878187376174123694673626\
70206140952496972477833456296346863423687600061250473256218862375058\
29850498789465971165745198240949077990186742066226067853556968987171\
9325372141858119131848179713

How could we determine the number of digits without having to use a tool like bc to print them out?
( log₁₀65537¹⁵⁴⁵¹ ) = ( 15451 log₁₀65537 ) ≈ 74,000

Let’s think about the cost of this operation in terms of computation and space. There will be 15,450 multiplication operations (a^n-1), and it will take almost 31k bytes to store a number 74,000 long.

How did we calculate the number of bytes?
Every 3 digits takes up to 10 bits of storage:

For example:
	100₂ = 0000 0000 0110 0100
	999₂ = 0000 0011 1110 0111

10 bits ≈ 3 decimals:
	log₂1024 = 10  <-- bits
	log₁₀1000 = 3  <-- decimals

74000 / 3 ≈ 24666 * 10 = 246660 / 8 ≈ 30,8333 bytes
Steps to calculate the storage needed for a 74,000 length number:

Divide the total length of the number by 3 digits (since that’s the basis for calculating the 10 bits).

Multiply by 10 bits.

Divide by 8 bits (one byte).

Ok, now that we understand the implications of the costs large exponentiations, is there anything we can do to improve it? Exponentiation is, after all, just repeated multiplication operations of the same base integer. Surely, that can be optimized!

Sí, seńor!

Exponentiation By Squaring

The good news is that we can greatly reduce the number of multiplication operations, the bad news is that it will still take up the same amount of storage in memory. This makes sense, since after all the number is what it is!

The idea behind exponentiation is that you can take shortcuts to achieve your objective. For instance, if we were to calculate 2⁸ naively, it would look like a brute-force approach:

2⁸ = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 256

This would amount to 7 multiplication operations (a^{n - 1}).

The better approach is to simply square the result of the prior computation!

Think of it this way:

2⁸ = ( ( ( 2² ) ² ) ² ) = 256

or:

2⁸ = a² * a² * a² * a² = 256

So, using the naive approach, it would take us 7 operations. Comparatively, our new approach only takes 3 (log₂8)! And this makes a difference in the orders of magnitude as the exponents get into the tens and hundreds of digits long.

Just For Fun

The following are all equivalent:

	2⁸ = 2^{2 + 2 + 2 +2}
	   = 2^{2 + 2 + 4}
	   = 2^{4 + 4}
	   = 256

	2⁸ = a² * a² * a² * a²
	   = a² * a² * a⁴
	   = a⁴ * a⁴
	   = 256

	2⁸ = 2^2² * 2^2²
	   = 2^2² * 2⁴
	   = 256

Explanation

Essentially, we only need to compute up to a^{n / 2}.

For example, if we’re computing the expression 3³², we only need to calculate up to 3¹⁶, because the last operation will square 3¹⁶ to reach the goal of 3³².

Let’s break that down:

a * a = a²
(a²)² = a⁴
(a⁴)² = a⁸
(a⁸)² = a¹⁶
(a¹⁶)² = a³²

Five operations versus 31!

Again, this is how we determine the number of multiplication operations:

	log_an

Example:
	aⁿ

	a = 2
	n = 32

	log₂32 = 5

Remember, logarithms are the opposite of exponentiations!

log₂4294967296 = 32

2³² = 4294967296

Implementation for Powers of Two

The following program written in C only calculates exponents that are powers of two. We’ll shortly see how we can also compute non-powers of two.

exponentiation_by_squaring_powers_of_two.c

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

// gcc -o exp2 exponentiation_by_squaring_powers_of_two.c -lm

int is_power_of_two(int n) {
    return (n & n - 1) == 0;
}

int main(int argc, char **argv) {
    if (argc < 2) {
        printf("[ERROR] Not enough args: %s [base] [exponent]\n", argv[0]);
        exit(1);
    }

    int exp = atoi(argv[2]);

    if (!is_power_of_two(exp)) {
        printf("[ERROR] Exponent `%d` is not a power of two, exiting.\n", exp);
        exit(1);
    }

    double res = atio(argv[1]);
    int i = 0;
    int e = (int) log2(exp);    // We only need to loop until the log2 of
				// the exponent since we're squaring!

    while (i < e) {
        res *= res;
        ++i;
    }

    // The results will always be whole numbers, so format as such.
    printf("%.0f\n", res);
    return 0;
}

Even though all of the examples in this article have used 2 as the base, this program will work for any base. The only requirement is that the exponent be a power of two.

For example:

gcc -o exp2 exponentiation_by_squaring_powers_of_two.c -lm

./exp2 2 32	// 4294967296
./exp2 3 16	// 43046721
./exp 5 128	// 293873587705571955623086381296639321901703084698483813243829625275718325188616411500511232

Ok, that’s cool, albeit limited. Let’s see how we can raise the base to any number!

Handling All Numbers

In order for us to handle any number as the exponent, we need to use an algorithm that can handle cases when the number is even and when it is odd at every step of the computation.

We’ve seen that an even exponent is halved to determine the number we need to calculate up to, but what about when the exponent is odd? In that case, we need to first subtract one before halving:

a^{n - 1} / 2

In addition, we’d need to multiply by a:

( a^{n - 1} / 2 ) * a

This makes sense. If we take the expression 2⁵, we need to first subtract one from the exponent 5 before we can halve it:

2⁵ = 2^{5 - 1} * 2
   = ( ( 2⁴ / 2 ) * 2 ) * 2
   = 32

Let’s look at an example recursively:

3¹³ = 1594323
3^{13 - 1} * 3 = 3¹² * 3
3^{12 / 2} = 3⁶
3^{6 / 2} = 3³
3^{3 - 1} * 3 = 3² * 3
3^{2 - 1} = 3¹
3 * 1

So, the base case will be 1.

The steps we’ll use to code this are the following:

Look at the exponent.
If odd, multiply by the base.
If equal to 1, return.
Else divide and repeat step 1.

This is pretty straightforward so far. The next step is how to determine if the exponent is odd or even at each step. The best way to do this is to decode the number from its decimal representation to raw bits.

asbits 13 1
1101

We’ll look at the lowest bit. This is what determines whether the current number is odd (1) or even (0).

1101 is odd. Multiply by a, subtract 1 from n and square.
- (13 - 1) / 2 = 6
110 is even. Square.
- 6 / 2 = 3
11 is odd. Multiply by a, subtract 1 from n and square.
- (3 - 1) / 2 = 1
1 is odd. Multiply by a.
Base case has been reached.

Implementation for All Powers

exponentiation_by_squaring.c

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

// gcc -o basex exponentiation_by_squaring.c -lm

void reverse(char *s) {
    int c, i, j;

    // Let's pretend there's no strlen function.
    for (j = 0; s[j] != '\0'; j++)
        ;

    for (i = 0, j--; i < j; i++, j--)
        c = s[i], s[i] = s[j], s[j] = c;
}

void getbits(int exp, char* buf) {
    int maxbits = (int) log2(exp);
    int i = 0;

    for (int n = exp; i <= maxbits; n >>= 1)
        buf[i++] = (n & 1) == 0 ?  '0' : '1';

    buf[i] = '\0';
    reverse(buf);
}

void main(int argc, char **argv) {
    if (argc < 3) {
        printf("[ERROR] Not enough args: %s [base] [exp]\n", argv[0]);
        exit(1);
    }

    int base = atoi(argv[1]);
    char buf[32];

    getbits(atoi(argv[2]), buf);

    double res = 1;
    int i = 0;

    while (buf[i] != '\0') {
        res *= res;

        if (buf[i++] == '1')
            res *= base;
    }

    printf("%.0f\n", res);
}

Note in the getbits function that we’re right shifting the number to “chop off” the lowest bit. This has the same result as dividing by 2 or halving.
  1101 then 1101 >> 1,
   110 then  110 >> 1,
    11 then   11 >> 1,
     1

Conclusion

Weeeeeeeeeeeeeeeeeeeeeeee