"As you can see, this young male stack frame is prowling through the forest of dense, tangled registers calling for a mate. Alas, with the stack currently empty, his efforts are unfortunately futile." *cue safari music*
I once tried to compute just a slightly bigger ackerman call like ack(3,3) computed in an instance and I tried ack(3,4) i think, but it exhausted the call stack. So I wrote the expansion to disk, to parse the deferred chain. The whole computation, even though it was just text, created a 10gb textfile while the slightly smaller call ack(3,3) just needed about 15lines of deferred chains. gives you a feeling of how insanely fast the output grows. This is due to the ackerman function actually abstracting hyperoperation. Where ack(3,3) was exponentiation, ack(3,4) was tetration. To put it simply: it is rasing exponentiation itself to a power. Then ack(3,5) would be even more extreme, a pentation - rasing the rasing of exponentation to a power, or just rasing tetration to a power.
example of enumerable recursion with occasional output: "Display all files in drive C" example of undescidable recursion: "write a text file that contains the hash value of the file when the file is hashed."
I remember when in school we were making the program that solved the “Hanoi tower” problem and then we made a fractal tree that was moving in the wind - it was so beautiful! Since that day I fell in love with recursions and fractals!
Recursively Enumerable includes undecidable problems. The halting problem is undecidable and recursively enumerable (just run the turing machine and accept if it halts). What you meant to put at the end is unrecognizable problems. An example of an unrecognizable problem is all turing machine input pairs that do not halt.
See the thing is, that's barely bigger than G64 already. It's actually smaller than G65 Ack(G64, G64) looks to be 2 ↑^(G64) (G64 + 3) whereas G65 = 3 ↑^(G64) G64 ↑^(G64) refers to G64 Knuth Arrows
i believe that for loops and recursion are only needed when working with indexes and such. but not when doing math... there is always an equation. that will do it next to instantly.
steven johnston No. Elementary functions can be defined recursively and there is no closed for solution to them. Some functions are defined as infinite sums of basis functions. Most differential equations have no closed for solutions and must be solved numerically. In all these cases, loops or recursions are absolutely necessary. And it's definitely not true that it can be computed instantly. I currently have 3 computers working for almost a month on one problem ;)
wuuut? i disagree math is all about recursion... the simplest of elements in math revolve around recursion like say counting but before we can count we have to define natural numbers; how do you define a number? well a number is either zero or the increment of a number, so you can practically create a function called "number 5" which is just inc^5(zero), see? recursion
int ack(int m, int n){ if(m==0)return n+1; if(n==0)return ack(m-1, 1); return ack(m-1, ack(m,n-1)); } here's a simple java version for anyone wanting to play with it, overflows pretty easily
At school while learning VB6 long time ago, I made a horse race game project. It had to have random values on the power of the horse but I felt that this PC random function was not enough random to me. So in the race the speed was randomly changing speed by a random factor for a random time. This is how you could have a 200MHz computer completely freeze. At that moment I understood that my code was not optimized.
The value of each iteration can be figured out using tetration. 2^^x 2 4 16 - 3 = 13 65536 - 3 = 65533 2.00353 × 10^19,728 - 3 = 2.00353 × 10^19,728 and so on
as he said that in the past it took 11 minutes and now he says - 10 years later, we are doing it in 3, so more than 3 times as fast, it will take less than a minute. that is if processing power doesn't have any leap forward.
It's important to point out that this guy is not a software engineer, otherwise he might have known that his code snippet needed indentation, that his computer doesn't have a Pentium, or that Haskell solves practically everything via recursion. Not that it matters, I mean after all he's obviously an expert in computational science.
Ironically using recursion for Ackermann function leads to serious technical problem: stack overflow. So you better convert it to iteration algorithm or reimplement the stack. Following C program prints all results of Ackermann function where result is within unsigned long int range. No recursion here, but it's very different approach, go through result values and determine what m,n it is an answer for. #include #include #include #define maxM 100 print_ack(int m, unsigned long int n, unsigned long int v) { printf("ack(%d,%ld)=%ld ", m, n, v); } main() { int i; unsigned long int val, n[maxM]={0}, v[maxM]; for (i = 1; i < maxM; i++) v[i]=-1; for (val = 1; val < ULONG_MAX; val++) { v[0] = val; print_ack(0, n[0], val); for(i=0; 1; i++) { if(n[i]==1) { v[i+1]=val; n[i+1]=0; print_ack(i+1, n[i+1], val); } else if(n[i]==v[i+1]) { v[i+1]=val; n[i+1]+=1; print_ack(i+1, n[i+1], val); } else break; } n[0]++; } }
As written, this program is certainly very long winded to compute. However, from what I can see, it does seem that at least some of its recursive nature can be removed. As written there is only 1 base case solution: Ack(0,n) = n+1, all other cases are defined recursively. However, from observing the results of the function, it appears that you can define some other non-recursive base cases. For example, Ack(1,n) = n+2. You can check and you'll see that any time the first parameter is 1 then the answer will always be 2 more than the 2nd parameter. Also, Ack(2,n) = 2n+3, again. And I'm slightly less confident, but still pretty sure that Ack(3,n) = 2^(n+3) - 3 If you were to implement these additional base cases into the program it would cut out a lot of the recursion required. I would imagine that it's probably possible to devise other base cases for other values of m, but it gets rather difficult due to the sheer growth. It may even be possible that there is a generalization for computing these base cases for any m, which could completely remove recursion (though that would require a far greater mind than my own). Anyways, assuming that my base case for Ack(3,n) is correct, as well as using previously calculated results, then I've managed to calculate Ack(4,2) in about a matter of seconds. Ack(4,2) would obviously become Ack(3,Ack(4,1)) -> Ack(3, 65533) and I've proposed a base case for that. So, assuming my base case is accurate, Ack(4,2) = 2^65536 - 3 I easily found an online calculator that could handle such an answer, it happens to be 19,729 digits long, so I can't exactly post it here. The base case for Ack(4,n) appears to be power-tower related, as the "known" values (including ack4,2) are: Ack(4,0) = 2^4 - 3 Ack(4,1) = 2^16 - 3 Ack(4,2) = 2^65536 - 3 So I assume that Ack(4,3) must be equal to 2^(2^(65536)) - 3 I tried to calculate this online as well, but couldn't find a calculator that would accept a nearly 19 thousand digit exponent :( But my point is, is that these values CAN, in fact, be calculated non-recursively.
Oh, you know what, Computerphile? You got this wrong. Right at 5:16, he says "look it gives back an integer result" and you highlighted "int m,n"--that is NOT the line that defines the type of the return value. It is the int before the ack that says the return value will be an integer.
When Prof. Brailsford talks about "derecursing", is he talking about corecursion? Where does duality fit in with each of these classes of problems, primitive recursive, recursive, and recursively enumerable?
I got it! Ackerman (4, 2), put those to numbers together. 42. Therefore, the final result of ackerman (4, 2) will be the answer to life, the universe, and everything, but in a different form. Obviously, it is going to take til the end of the universe for us to find Ackerman (4,2) on a linux machine, we nee something much more powerful like Deep Thought.
With various optimizations in C++ I can get ackermann(4,2) pretty much instantly. With more optimizations my computer locks up attempting ackermann(4,3). Give it enough stack to not segfault and it just locks the whole thing up. I wasn't expecting my computer to be sufficiently faster than the Professors to actually get a result within my lifetime, but it was a fun attempt.
I solved ack(4, 2). It took my computer quite some time. 2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880933348101038234342907263181822949382118812668869506364761547029165041871916351587966347219442930927982084309104855990570159318959639524863372367203002916969592156108764948889254090805911457037675208500206671563702366126359747144807111774815880914135742720967190151836282560618091458852699826141425030123391108273603843767876449043205960379124490905707560314035076162562476031863793126484703743782954975613770981604614413308692118102485959152380195331030292162800160568670105651646750568038741529463842244845292537361442533614373729088303794601274724958414864915930647252015155693922628180691650796381064132275307267143998158508811292628901134237782705567421080070065283963322155077831214288551675554073345107213112427399562982719769150054883905223804357045848197956393157853510018992000024141963706813559840464039472194016069517690156119726982337890017641517190051133466306898140219383481435426387306539552969691388024158161859561100640362119796101859534802787167200122604642492385111393400464351623867567078745259464670903886547743483217897012764455529409092021959585751622973333576159552394885297579954028471943529913543763705986928913757153740001986394332464890052543106629669165243419174691389632476560289415199775477703138064781342309596190960654591300890188887588084733625956065444888501447335706058817090162108499714529568344061979690565469813631162053579369791403236328496233046421066136200220175787851857409162050489711781820400187282939943446186224328009837323764931814789848119452713007440220765680910376203999203492023906626264491909167985461515778839060397720759279378852241294301017458086862263369284725851403039615558564330385450688652213114813638408384778263790459607186876728509763471271988890680478243230394718650525660978150729861141430305816927924971409161059417185352275887504477592218301158780701975535722241400019548102005661773589781499532325208589753463547007786690406429016763808161740550405117670093673202804549339027992491867306539931640720492238474815280619166900933805732120816350707634351669869625020969023162859350071874190579161241536897514808261904847946571736601005892476655445840838334790544144817684255327207315586349347605137419779525190365032198020108764738368682531025183377533908861426184800374008082238104076468878471647552945326947661700424461063311238021134588694532200116564076327023074292426051582811070387018345324567635625951430032037432740780879056283663406965030844225855967039271869461158513793386475699748568670079823960604393478850861649260304945061743412365828352144806726676841807083754862211408236579802961200027441324438432402331257403545019352428776430880232850855886089962774458164680857875115807014743763867976955049991643998284357290415378143438847303484261903388841494031366139854257635577105335580206622185577060082551288893332226436281984838613239570676191409638533832374343758830859233722284644287996245605476932428998432652677378373173288063210753211238680604674708428051166488709084770291208161104912555598322366244868556651402684641209694982590565519216188104341226838996283071654868525536914850299539675503954938371853405900096187489473992880432496373165753803673586710175783994818471798498246948060532081996066183434012476096639519778021441199752546704080608499344178256285092726523709898651539462193004607364507926212975917698293892367015170992091531567814439791248475706237804600009918293321306880570046591458387208088016887445835557926258465124763087148566313528934166117490617526671492672176128330845273936469244582892571388877839056300482483799839692029222215486145902373478222682521639957440801727144146179559226175083889020074169926238300282286249284182671243405751424188569994272331606998712986882771820617214453142574944015066139463169197629181506579745526236191224848063890033669074365989226349564114665503062965960199720636202603521917776740668777463549375318899587866282125469797102065747232721372918144666659421872003474508942830911535189271114287108376159222380276605327823351661555149369375778466670145717971901227117812780450240026384758788339396817962950690798817121690686929538248529830023476068454114178139110648560236549754227497231007615131870024053910510913817843721791422528587432098524957878034683703337818421444017138688124249984418618129271198533315382567321870421530631197748535214670955334626336610864667332292409879849256691109516143618601548909740241913509623043612196128165950518666022030715613684732364660868905014263913906515063908199378852318365059897299125404479443425166774299659811849233151555272883274028352688442408752811283289980625912673699546247341543333500147231430612750390307397135252069338173843322950701049061867539433130784798015655130384758155685236218010419650255596181934986315913233036096461905990236112681196023441843363334594927631946101716652913823717182394299216272538461776065694542297877071383198817036964588689811863210976900355735884624464835706291453052757101278872027965364479724025405448132748391794128826423835171949197209797145936887537198729130831738033911016128547415377377715951728084111627597186384924222802373441925469991983672192131287035585307966942713416391033882754318613643490100943197409047331014476299861725424423355612237435715825933382804986243892498222780715951762757847109475119033482241412025182688713728193104253478196128440176479531505057110722974314569915223451643121848657575786528197564843508958384722923534559464521215831657751471298708225909292655638836651120681943836904116252668710044560243704200663709001941185557160472044643696932850060046928140507119069261393993902735534545567470314903886022024639948260501762431969305640666366626090207048887438898907498152865444381862917382901051820869936382661868303915273264581286782806601337500096593364625146091723180312930347877421234679118454791311109897794648216922505629399956793483801699157439700537542134485874586856047286751065423341893839099110586465595113646061055156838541217459801807133163612573079611168343863767667307354583494789788316330129240800836356825939157113130978030516441716682518346573675934198084958947940983292500086389778563494693212473426103062713745077286156922596628573857905533240641849018451328284632709269753830867308409142247659474439973348130810986399417379789657010687026734161967196591599588537834822988270125605842365589539690306474965584147981310997157542043256395776070485100881578291408250777738559790129129407309462785944505859412273194812753225152324801503466519048228961406646890305102510916237770448486230229488966711380555607956620732449373374027836767300203011615227008921843515652121379215748206859356920790214502277133099987729459596952817044582181956080965811702798062669891205061560742325686842271306295009864421853470810407128917646906550836129916694778023822502789667843489199409657361704586786242554006942516693979292624714524945408858422726153755260071904336329196375777502176005195800693847635789586878489536872122898557806826518192703632099480155874455575175312736471421295536494084385586615208012115079075068553344489258693283859653013272046970694571546959353658571788894862333292465202735853188533370948455403336565356988172582528918056635488363743793348411845580168331827676834646291995605513470039147876808640322629616641560667508153710646723108461964247537490553744805318226002710216400980584497526023035640038083472053149941172965736785066421400842696497103241919182121213206939769143923368374709228267738708132236680086924703491586840991153098315412063566123187504305467536983230827966457417620806593177265685841681837966106144963432544111706941700222657817358351259821080769101961052229263879745049019254311900620561906577452416191913187533984049343976823310298465893318373015809592522829206820862230332585280119266496314441316442773003237792274712330696417149945532261035475145631290668854345426869788447742981777493710117614651624183616680254815296335308490849943006763654806102940094693750609845588558043970485914449584445079978497045583550685408745163316464118083123079704389849190506587586425810738422420591191941674182490452700288263983057950057341711487031187142834184499153456702915280104485145176055306971441761368582384102787659324662689978418319620312262421177391477208004883578333569204533935953254564897028558589735505751235129536540502842081022785248776603574246366673148680279486052445782673626230852978265057114624846595914210278122788941448163994973881884622768244851622051817076722169863265701654316919742651230041757329904473537672536845792754365412826553581858046840069367718605020070547247548400805530424951854495267247261347318174742180078574693465447136036975884118029408039616746946288540679172138601225419503819704538417268006398820656328792839582708510919958839448297775647152026132871089526163417707151642899487953564854553553148754978134009964854498635824847690590033116961303766127923464323129706628411307427046202032013368350385425360313636763575212604707425311209233402837482949453104727418969287275572027615272268283376741393425652653283068469997597097750005560889932685025049212884068274139881631540456490350775871680074055685724021758685439053228133770707415830756269628316955687424060527726485853050611356384851965918968649596335568216975437621430778665934730450164822432964891270709898076676625671517269062058815549666382573829274182082278960684488222983394816670984039024283514306813767253460126007269262969468672750794346190439996618979611928750519442356402644303271737341591281496056168353988188569484045342311424613559925272330064881627466723523751234311893442118885085079358163848994487544756331689213869675574302737953785262542329024881047181939037220666894702204258836895840939998453560948869946833852579675161882159410981624918741813364726965123980677561947912557957446471427868624053750576104204267149366084980238274680575982591331006919941904651906531171908926077949119217946407355129633864523035673345588033313197080365457184791550432654899559705862888286866606618021882248602144999973122164138170653480175510438406624412822803616648904257377640956326482825258407669045608439490325290526337532316509087681336614242398309530806549661879381949120033919489494065132398816642080088395554942237096734840072642705701165089075196155370186264797456381187856175457113400473810762763014953309735174180655479112660938034311378532532883533352024934365979129341284854970946826329075830193072665337782559314331110963848053940859283988907796210479847919686876539987477095912788727475874439806779824968278272200926449944559380414608770641941810440758269805688038949654616587983904660587645341810289907194293021774519976104495043196841503455514044820928933378657363052830619990077748726922998608279053171691876578860908941817057993404890218441559791092676862796597583952483926734883634745651687016166240642424241228961118010615682342539392180052483454723779219911228595914191877491793823340010078128326506710281781396029120914720100947878752551263372884222353869490067927664511634758101193875319657242121476038284774774571704578610417385747911301908583877890152334343013005282797038580359815182929600305682612091950943737325454171056383887047528950563961029843641360935641632589408137981511693338619797339821670761004607980096016024823096943043806956620123213650140549586250615282588033022908385812478469315720323233601899469437647726721879376826431828382603564520699468630216048874528424363593558622333506235945002890558581611275341783750455936126130852640828051213873177490200249552738734585956405160830583053770732533971552620444705429573538361113677523169972740292941674204423248113875075631319078272188864053374694213842169928862940479635305150560788126366206497231257579019598873041195626227343728900516561111094111745277965482790471250581999077498063821559376885546498822938985408291325129076478386322494781016753491693489288104203015610283386143827378160946341335383578340765314321417150655877547820252454780657301342277470616744241968952613164274104695474621483756288299771804186785084546965619150908695874251184435837306590951460980451247409411373899927822492983367796011015387096129749705566301637307202750734759922943792393824427421186158236161317886392553095117188421298508307238259729144142251579403883011359083331651858234967221259621812507058113759495525022747274674369887131926670769299199084467161228738858457584622726573330753735572823951616964175198675012681745429323738294143824814377139861906716657572945807804820559511881687188075212971832636442155336787751274766940790117057509819575084563565217389544179875074523854455200133572033332379895074393905312918212255259833790909463630202185353848854825062897715616963860712382771725621313460549401770413581731931763370136332252819127547191443450920711848838366818174263342949611870091503049165339464763717766439120798347494627397822171502090670190302469762151278521956142070806461631373236517853976292092025500288962012970141379640038055734949269073535145961208674796547733692958773628635660143767964038430796864138563447801328261284589184898528048048844180821639423974014362903481665458114454366460032490618763039502356402044530748210241366895196644221339200757479128683805175150634662569391937740283512075666260829890491877287833852178522792045771846965855278790447562192663992008409302075673925363735628390829817577902153202106409617373283598494066652141198183810884515459772895164572131897797907491941013148368544639616904607030107596818933741217575988165127000761262789169510406315857637534787420070222051070891257612361658026806815858499852631465878086616800733264676830206391697203064894405628195406190685242003053463156621891327309069687353181641094514288036605995220248248886711554429104721929134248346438705368508648749099178812670565665387191049721820042371492740164460943459845392536706132210616533085662021188968234005752675486101476993688738209584552211571923479686888160853631615862880150395949418529489227074410828207169303387818084936204018255222271010985653444817207470756019245915599431072949578197878590578940052540122867517142511184356437184053563024181225473266093302710397968091064939272722683035410467632591355279683837705019855234621222858410557119921731717969804339317707750755627056047831779844447637560254637033369247114220815519973691371975163241302748712199863404548248524570118553342675264715978310731245663429805221455494156252724028915333354349341217862037007260315279870771872491234494477147909520734761385425485311552773301030342476835865496093722324007154518129732692081058424090557725645803681462234493189708138897143299831347617799679712453782310703739151473878692119187566700319321281896803322696594459286210607438827416919465162267632540665070881071030394178860564893769816734159025925194611823642945652669372203155504700213598846292758012527715422016629954863130324912311029627923723899766416803497141226527931907636326136814145516376656559839788489381733082668779901962886932296597379951931621187215455287394170243669885593888793316744533363119541518404088283815193421234122820030950313341050704760159987985472529190665222479319715440331794836837373220821885773341623856441380700541913530245943913502554531886454796252260251762928374330465102361057583514550739443339610216229675461415781127197001738611494279501411253280621254775810512972088465263158094806633687670147310733540717710876615935856814098212967730759197382973441445256688770855324570888958320993823432102718224114763732791357568615421252849657903335093152776925505845644010552192644505312073756287744998163646332835816140330175813967359427327690448920361880386754955751806890058532927201493923500525845146706982628548257883267398735220457228239290207144822219885587102896991935873074277815159757620764023951243860202032596596250212578349957710085626386118233813318509014686577064010676278617583772772895892746039403930337271873850536912957126715066896688493880885142943609962012966759079225082275313812849851526902931700263136328942095797577959327635531162066753488651317323872438748063513314512644889967589828812925480076425186586490241111127301357197181381602583178506932244007998656635371544088454866393181708395735780799059730839094881804060935959190907473960904410150516321749681412100765719177483767355751000733616922386537429079457803200042337452807566153042929014495780629634138383551783599764708851349004856973697965238695845994595592090709058956891451141412684505462117945026611750166928260250950770778211950432617383223562437601776799362796099368975191394965033358507155418436456852616674243688920371037495328425927131610537834980740739158633817967658425258036737206469351248652238481341663808061505704829059890696451936440018597120425723007316410009916987524260377362177763430621616744884930810929901009517974541564251204822086714586849255132444266777127863728211331536224301091824391243380214046242223349153559516890816288487989988273630445372432174280215755777967021666317047969728172483392841015642274507271779269399929740308072770395013581545142494049026536105825409373114653104943382484379718606937214444600826798002471229489405761853892203425608302697052876621377373594394224114707074072902725461307358541745691419446487624357682397065703184168467540733466346293673983620004041400714054277632480132742202685393698869787607009590048684650626771363070979821006557285101306601010780633743344773073478653881742681230743766066643312775356466578603715192922768440458273283243808212841218776132042460464900801054731426749260826922155637405486241717031027919996942645620955619816454547662045022411449404749349832206807191352767986747813458203859570413466177937228534940031631599544093684089572533438702986717829770373332806801764639502090023941931499115009105276821119510999063166150311585582835582607179410052528583611369961303442790173811787412061288182062023263849861515656451230047792967563618345768105043341769543067538041113928553792529241347339481050532025708728186307291158911335942014761872664291564036371927602306283840650425441742335464549987055318726887926424102147363698625463747159744354943443899730051742525110877357886390946812096673428152585919924857640488055071329814299359911463239919113959926752576359007446572810191805841807342227734721397723218231771716916400108826112549093361186780575722391018186168549108500885272274374212086524852372456248697662245384819298671129452945515497030585919307198497105414181636968976131126744027009648667545934567059936995464500558921628047976365686133316563907395703272034389175415267500915011198856872708848195531676931681272892143031376818016445477367518353497857924276463354162433601125960252109501612264110346083465648235597934274056868849224458745493776752120324703803035491157544831295275891939893680876327685438769557694881422844311998595700727521393176837831770339130423060958999137314684569010422095161967070506420256733873446115655276175992727151877660010238944760539789516945708802728736225121076224091810066700883474737605156285533943565843756271241244457651663064085939507947550920463932245202535463634444791755661725962187199279186575490857852950012840229035061514937310107009446151011613712423761426722541732055959202782129325725947146417224977321316381845326555279604270541871496236585252458648933254145062642337885651464670604298564781968461593663288954299780722542264790400616019751975007460545150060291806638271497016110987951336633771378434416194053121445291855180136575558667615019373029691932076120009255065081583275508499340768797252369987023567931026804136745718956641431852679054717169962990363015545645090044802789055701968328313630718997699153166679208958768572290600915472919636381673596673959975710326015571920237348580521128117458610065152598883843114511894880552129145775699146577530041384717124577965048175856395072895337539755822087777506072339445587895905719156733
I did it mathematically and got the same answer: 2**(65533+3)-3 Actually I tweaked the algorithm to get rid of some recursions, to be able to calculate this quicker. if m == 0: ans = n + 1 elif m == 1: ans = n + 2 elif m == 2: ans = 2 * n + 3 elif m == 3: ans = 2 ** (n + 3) - 3 elif n == 0: ans = ack(m - 1, 1) else: ans = ack(m - 1, ack(m, n - 1)) I wanted to continue to m == 4, but seeing that number I lost the will to continue.
My linux box with default stack overflowed the stack before getting ackermann(4,1) of course there is no check for stack exhaustion, so absent any checking it blithely continues and computes it.
Why do you keep saying that "some problems HAVE to be done recursively"?.. any problem can be implemented with for/while loops because recursion is based on the stack and you can build your own stack with iterrative code. I can write you a pretty easy code in C/C++ that computes ackermann without using recursion.
Only if you have enough computing elements to store the answer, which in this case would take up more space than the universe even if it were as dense as a singularity...
At the end of the Three Body Problem, with the Universe collapsing into two dimensionality and people coming out of their pocket universes to contribute critical matter to aid it's rebirth, I bet out of camera shot there is someone at an intergalactic mainframe terminal who just got the answer to this and is hoping they can skim-read the 20000 decimal places before the big crunch happens just to say "we did it, I saw the answer!"
I implemented memoization, but due to limits with the stack I still cant compute (4,2). but (4,1) was instant, I also got up to (3, 21) : 16,777,213 With memoization, I figured out that to compute (m,n+1), it is double the operations it takes for (m,n)
Why are so many of those ackerman results a power of two, minus three? It holds continuously from (2,5) to (4,1) ... and with that stunning 65,533 on the end :O
I realize this video is nearly 4 years old and the chances of comments not seen are great, but does anyone know about how the code was compiled and run? I wrote an ANSI C version of the code shown on an Ubuntu machine and within minutes it returns a segmentation fault when computing 4,2, let alone running it for how long is claimed in the video. This was compiled with gcc, but with all default values.
cool video. but the big crunch will never happen; dark energy forces the universe to expand infinitely and exponentially. Unless the big rip occurs, your computer can finish the computation as long as it has power. Luckily, the infinite expansion is called "heat death", so the computer will become progressively colder, and the maximum speed and energy efficiency increase as the temperature drops. How long it can actually go on is related to the rate of temperature drop in proportion to the efficiency gain. I'm sure the calculation is tractable, but I'm not quite curious enough to do it.
On your previous video I played with factorials (in Visual Basic) doing this : Dim n As Integer = factorial(n) Or for all those C/C++ coders it translate : int n = factorial(n); (not sure in C/C++ it will compile, too lazy to try it on C) Of course I got overflow and it crash, but what about : ackermann(ackermann(ackermann, ackermann), ackermann(ackermann, ackermann)) ? :D Or even worst : ackermann(ackermann(ackermann(rnd), ackermann(rnd)), ackermann(ackermann(rnd), ackermann(rnd))) You are sure the first will never end and will goes on for ever trying to find out what he is himself (if it compile) But the second with (rnd) for random might reach a ridiculous proportion before you even realise it :D Edit : Ho and technically I can make it non recursive, I've done an experiment and write a Quick Sort and a Merge Sort algorithm the same way they should work recursively but using an array (that does the same job as the stack) and it can goes on until it finish using a "for loop", the only limit is the overflow with the array size, but if you can you can use multiple array, array_n(address) that when a first one get too large lets say array_0(maxaddress), you switch to array_1(0) and so one, which will lead to being able to do the equivalent of recursion inside recursion using an iterative program with only limit your memory (and even here you can write files and free some array to use your whole HDD to have even more false recursion going on) !
basically it's interesting if you like studying theoretical software. It's some interesting concepts, but it's utterly useless for actually writing software. This would do essentially the same thing: #include . . . double time; increase(time, time); sleep( time ); . . . double increase( double time, double temp_time) { time = pow(2, increase(time, temp_time-1); return time; } it's clunky but I'm not going to bother optimizeing and cleaning it up. it basically sleeps for 2^time!, or two raised to time factorial. Edit: at least as far as wasting cycles it would behave simularly
+Herp Derpington Actually, I still think it would terminate, because once m and n get small enough, the sign bit will flip and suddenly we're back at a positive number.
@@EmptyKingdoms For the purpose of explaining, consider this: In principle, you can represent a large number by its digits, and turn the multiplication with pencil and paper method ('schoolbook multiplication') into a program. It can handle anything that your computer can store. (280 lines of characters is like *nothing* compared to GBs of RAM) It won't be fast, but it shouldn't be too slow either. Now you can just start from 3 and keep multiplying by 2, which is again slow but shouldn't be unbearable. (You can even specialize and just write a 'multiply by single digit number' function) There are faster ways to do multiplication (google 'integer multiplication algorithm'), and also for exponentiation, but I'm not really familiar with those, but they are pretty well researched by others so maybe just consult what others already wrote. But actually, big integer implementations, or arbitrary precision integer implementations (look ma, no precision loss for final digits) use binary internally (bytes and words are just chunks of binary bits). 3 * 2**65533 is really neat in binary, so the real deal is converting it to decimal. Again, someone else already figured it out like ages ago. Just google 'radix conversion algorithm'. But why computers sometimes can't handle large numbers? Because really they just can't handle them *fast*. Like *real* fast. Your CPU has dedicated *hardware* circuitry to handle not too large integers and not too wild floats, so that if your program does not need 'weird' computation like computing a very large number it ends up blazingly fast, and most programs actually do just need normal numbers.
Minox sta summing positive integers is not supposed to be negative. But 1 + 2 + 3 + 4 + 5 + ... = -1/12 (see numberphile) So if string theory can incorporate that, why not ?
g64 is graham's number (see one of Brady's other videos). I first saw Ack(g64, g64) in an xkcd comic though. So you're looking at a number created through superexponential means, fed into a function that has a super exponential time complexity.
Sir, thank you for this. From app engineers to web developers, I’ve always felt that it is vitally important for programmers to study the mathematical properties that make our projects work. To do otherwise, to me, is like trying to be a materials engineer without having an understanding of the physical and chemical properties of your raw materials.
9:45 I reproduced the function in Python and believe I got it right as it gives me the same results, except for ack(4, 1): _"RecursionError: maximum recursion depth exceeded while calling a Python object"_ lulz at Python
You know you're a true mathematician when you get scared by how big a number can get. Also makes you appreciate how big infinity actually is. It's bigger than any ack out there.
Well, infinity isn’t bigger than any number. Infinity is an undefined value, so it cannot be compared to numbers. For example, you may be tempted to say that 1/0 is infinity because division by a value extremely close to zero results in an extremely huge number, but it’s technically undefined. The reason why it’s crazy to try to comprehend the “hugeness” of infinity is only because that for any number you come up with, you can always add one to it (or do some crazy operation) and it’s even bigger. It goes from incomprehensible to even more incomprehensible. Just wanted to say that infinity isn’t comparable to numbers, but more just an undefined thing that *does not exist in the set of real numbers.* (That’s an obvious fact, but with that in mind, it should also be obvious that saying infinity is bigger than a number is just as senseless as saying infinity is smaller than a number, because they’re apples and oranges.) Moreover, since 1/x has the limit of “positive” and “negative” infinity as x approaches zero from the right and left side respectively, that should clearly indicate that there is only one infinity, and that is the state of being undefined, not existing within the set of real numbers. When 1/x shoots down toward “negative” infinity from the left and comes back down from “positive” infinity after x passes through zero, that’s the function 1/x escaping the set of real numbers to a single place, called undefined, and returning to the set of real numbers in the same direction in which it exited. That said, infinity seems like it exists on either “end” of the real number line, so that would mean it’s just as correct to say that infinity is smaller than every single number you can think of. But if that was true, then it’s a contradiction. Infinity cannot be both bigger than and smaller than every real number, and hence it does not exist on either end of the real number line. The existence of infinity is entirely outside of the set of real numbers. So, finally, infinity cannot be compared to real numbers. It’s not bigger than any ack out there. It’s just that you can construct a number arbitrarily large enough to be bigger than any ack out there, and that’s what is mind-boggling. :)
All the cores in the world won't help you since this C code will run in a single thread. Also the first thing I thought was "wouldn't memoisation help improve performance?" After a quick google search, I discovered that "When a software developer learns about the Ackermann function, he will try to see how much of improvement function memoisation does if any". LOL
After breaking various online 'big number calculators' I found one that works, and it turns out 2^65533 * 3 minutes rounds out to, unless I've screwed up somewhere, about 1x10^19712 times the age of the universe. Not terribly helpful. (((((2^65533 * 3) / 60) / 24) / 365) / 13700000000) = 1.0434008320186794 × 10^19712
If you want help with big powers like that, try making logarithms of everything; multiplying and dividing stuff like that turns into adding and subtracting more manageable numbers.
You could try writing a memoized version of this code, where it remembers the result of a previous computation, and just plops that result in so it won't have to spend time working that out, cuz it seems to me that that's what's slowing it down so much; that it has to go through the same set of computations again and again EDIT: PEOPLE before commenting on why it wouldn't work; please read the other comments! THEY MAY ALREADY HAVE COME TO THE SAME CONCLUSION! Please don't waste precious keystrokes on repeated information, thank you
Nikolaj Lepka As far as I know your approach is known as " backtracking " , so for the people saying it wont work , it will. It will indeed make it faster.
The salad is strong in this one. You are already at the magnitude of TREE(3), doing an ackermann function (which is EXTREMELY weak by comparison) won't really do anything.
The TREE function is way stronger than the Ackermann function. However, the follow-up video of this video was about a function even stronger than the TREE function - the Busy Beaver function.
Hi Professor Brailsford! I've really enjoyed all your videos, thank you for taking the time to make them. It has been a couple years for me since graduating, and I miss my senior level computer science classes. Your lectures remind me of why I got in to and love the field... and not for a day job
It seems that some reductions can be made in the levels of recursion by adding cases for the following: ack(1, n) = n + 2 ack(2, n) = 2*n + 3 ack(3, n) = 1
Another optimization is to convert one of the tail-calls into a loop, that leaves us with just 1 recursive call. But thanks to your comment I realized there's a simpler way to optimize the A function, define it in terms of a single Hyper-Operation call: A(m, n) = HyperOP(m, 2, n + 3) - 3 Where the 0th argument of HP is the degree or "order" of the HyperOP we want to use, 1st arg is what we want to hyper-operate, and 2nd arg is the number of times to apply the "sub-HP". To implement HP efficiently, define it like so: HP(0, a, b) = b++ //add 1 HP(1, a, b) = a + b HP(2, a, b) = a × b HP(3, a, b) = a ^ b //a ** b The general case HP(n, a, b) requires recursion, it can be an implicit or explicit stack. It's essentially HP(n - 1, a, HP(n - 1, a, ...)), with b copies of HP calls, IIRC. HP(4, a, b) is tetration, HP(5, a, b) is pentation, etc... Before I realized this optimization, I just used the Wikipedia table with all closed-form expressions that didn't require recursion, and used a memoization hash table when recursion was needed. After implementing the HP optimization I realized Wikipedia already mentioned that in the "Definition" section, but I didn't understand the notation before... *bruh*
His computer's a bit slow. I compiled his function pretty much verbatim, and it calculates ack(4,1) in 27 seconds. With optimized compilation, it only takes 5.7 seconds. I don't think I'll bother calculating ack(4,2) though...
+moveaxebx The Ackermann function is not tail recursive. That is essentially what the professor is explaining. Tail call optimization is, in a sense, converting a recursion into a for loop (making it iterative), and you can not do this for functions like ack.
This video taught me how to crash a C++ compiler! template struct Ack { static constexpr size_t value = Ack::value; }; template struct Ack { static constexpr size_t value = Ack::value; }; template struct Ack { static constexpr size_t value = n + 1; }; template struct Ack { static constexpr size_t value = 1; };
I downloaded the program files and ran ack(6,6) on my quad core 3.2 ghz machine running Arch Linux. It used 100% of one of my cores, took 1 minute 45 seconds, and ended in a segmentation fault. ack(4,4) also segfaults. ack(3,3) returns in under a second.
Joseph Harrietha Since the Ackermann function is a classic in theoretical computer science, QC being only theoretical at the time being shouldn't matter all that much for the question at hand ;)
Would caching make this function more computable? By remembering old results you do not need to recalculate them. Since it only calls the function with reduced arguments, it doesn't seem that hard to build your way up? I am probably missing something :P
I've been jobbing business focused programmer for over thirty years. I was at college recursion was kind of worshiped by my tutors 'oh look at the elegant code' they would say. When I got in to the business world the number of times recursion was the best solution was about twice in thirty years!
u guys never sorted anything? i would assume most sort functions are recursive (of course i could be totally wrong - but then again i could be totally right!)? Or do you mean you never had to write any recursive code?
Strangely no because whenever I've had data it's been inside a database, so you get the database to sort the data before you get the data out. Or if you get it into a webpage then use methods from a library like jQuery datatables to handle the sorting for you. I've never needed to get my hands dirty sorting. Infact I remeber doing all that sorting stuff at college level and pretty much never having to use it like I never used truth tables or Karnough maps!
Steve Gould haha yeah - it's the curse (?) of software engineering, learn the nuts and bolts but unless you plan to be an expert on, say sorting, you are better off using someone else's sorting routines - so why learn the nuts and bolts in the 1st place. My answer would be: for job interviews! lol! cheers!
Spot on DjDedan and in fact some the most successful 'programmers' I know hardly write a line of code. They are just very good a cobbling together solutions from other people's work.
It's been 15 years I'm working professionally in computer science, writing code and doing something useful with it, thinking that I'm kind of understanding how it all works, from the theory of electronics, to the end user using it, I'm mind blown that some mathematician from the early 20s have already thought of all of this. Plus kudos to mr Brallsford explaining it like it's some basic course by its concise explaination. Love from France
Now, here is the nasty thing. You can program Ackermann's function iteratively. It requires setting up a stack and it is not a pretty picture. But you can do it. Those of you aware that no machine language actually has any recursion in it could probably guess this fact.
That's not the point. The point is you can't convert a general recursive function into a FOR loop. Of course, you can convert it into a while loop. You just can not know maximum possible iterations. That's why you can't do a for loop. Also, machine languages has recursion in it. Recursion basically means calling the currently executing subroutine. What prevents you from doing it? For example, in x86 assembly, you can just use the call instruction.
@@aim2986 Yes you can use the call instruction. But it is not innately recursive, as you will find out when you mess up your stack. It is an iterative instruction. It saves some data to memory, updates a general purpose register and updates the instruction pointer. I stand by my statement. No machine language _actually_ has recursion in it. It has tools you can use to implement recursive algorithms.
@@PvblivsAelivs by that logic no machine language actually has functions in it, too. We can think all non-recursive functions like loops which iterate only once. Like a do..while(false) loop.
@@PvblivsAelivs ok. I got you. Machine languages doesn't have functions. But I think assembly languages does. I know that's not the point here, but I just wanted to make it clear. Because you know, we can define labels which we can jump later.
I don't know. That's cool that they are powers of 2 minus 3! 👍 I like powers of 2. The Ack(4,1) value of 65,533 is 3 less than 2^16. 😀 These are amazing and intriguing things on this video!
The piece of code shown is K&R c code style (not ANSI c). stackoverflow.com/a/1630645/4824854 Please, don't show it on UA-cam, people will code badly. Thanks for everything else.
You've discussed algorithms that are necessarily recursive. Given that multi-cores and threads are now mainstream, I wonder if there are any algorithms that are necessarily parallel.
Jonathan Park I meant that you can always emulate a parallel machine on a serial one. This means that there are no problems that are solvable by parallel but not by serial one.
Jonathan Park You can call it this way. I answered to "I wonder if there are any algorithms that are necessarily parallel." And since you can convert any parallel algorithm to a serial one (even if that means emulating some parallel machine), then parallel algorithms can't solve any problem that a serial algorithm can't.
I worked out the fast Ackermann function :) function fAck(m,n){ var ack = [4,5,6,2,3,4,5,6,7,3,5,7,9,11,13,5,13,29,61,125,253,13,65533]; console.log( ack[m] ) if( m
I have a different idea--what if we remembered the results of every call, so we could look them up in a table rather than recalculating? Would that simplify the problem? Somewhat at least. We are calling ack with the same values over and over. But is it enough? Interesting. By remembering the previous values, my program is able to calculate ack(4,1) instantaneously as 65,533. So remembering the previous values does simplify the problem, but I still get a stack error before I get to ack(4,2). Here's a question. Since there is an obvious pattern to the answers, what if we just rewrite ack to return the value? Is that possible? Or is recursion still necessary in order to calculate the n^n . . . ^n . . . ^n?
Yeah I was thinking of turning this into a math problem to look for shortcuts for 10,10. Maybe if they understood the math it can be written easier. Then you only have a fraction of the work to do.
As this problem is computable via µ-recursion, it is also computable by while-loops, this may speed your calculation up. For the problem of n^n^...^n^n (a power-tower) this can actualy be done with for-loops or primitive recursion, so the computational time is not that bad: In Python: def pt(x, y): n = x for i in range(y): n = x ** n return n The main problem here is that the numbers also become quite huge and may not fit into memory.
Computerphile is such a wonderful treat for me, thank you so much Brady and all of your interviewees for the time and effort putting this together (numberphile as well!). You are doing a service to all mankind, you deserve a trophy!
Ackermann was clearly a very naughty boy. The man's created a monstrosity. Imagine feeding it into the Krell Machine and saying, "chew on that, motherflocker!" as the core starts to overheat with Robbie in the background chiming, "warning, warning, what you have done is wrong" and the Id becomes furious and is going to have you!
one question about this: when I wrote this in python I got an error that more than 1000 recursive calls is not possible. While this might be different in other programming languages I'm a bit baffled that this can run for four weeks on their computer and not lead to some memory problem... Cause isn't the thing about recursiveness that we need absurd amounts of memory?
+Ezechielpitau > " isn't the thing about recursiveness that we need absurd amounts of memory?" Tail-call optimization completely eliminates the memory problem, if the programmer makes an effort to lay out the function in a certain way.
+Paulina Jonušaitė I believe that will only work for primitive recursive functions. In this case, one branch has a recursive call that cannot be unrolled.
He's could be the David Attenborough of computer science. "...And here, we observe the C++, in its natural habitat..."
Nailed it
"As you can see, this young male stack frame is prowling through the forest of dense, tangled registers calling for a mate. Alas, with the stack currently empty, his efforts are unfortunately futile."
*cue safari music*
That's who he reminds me of!
"but alas, the buffer overflowed and as you see can see the instruction pointer makes a miraculous jump towards the kernel"
hahaha
I once tried to compute just a slightly bigger ackerman call like ack(3,3) computed in an instance and I tried ack(3,4) i think, but it exhausted the call stack. So I wrote the expansion to disk, to parse the deferred chain. The whole computation, even though it was just text, created a 10gb textfile while the slightly smaller call ack(3,3) just needed about 15lines of deferred chains.
gives you a feeling of how insanely fast the output grows. This is due to the ackerman function actually abstracting hyperoperation. Where ack(3,3) was exponentiation, ack(3,4) was tetration. To put it simply: it is rasing exponentiation itself to a power. Then ack(3,5) would be even more extreme, a pentation - rasing the rasing of exponentation to a power, or just rasing tetration to a power.
Keist Zenon just to blow your mind even more, pentation isnt raising tetration to a power, its raising tetration to a tetration
So it acts like Graham's number?
Similar, but Graham is kinda one level above Ackermann.
I wrote 3, 4 in C and it was actually instantaneous. Although 4, 4 caused a buffer overflow
@@DenisovichDev he was parsing the deferred chains. You didn't so that why yours was instant.
I just love that you can look at his face an see how much he loves this topic
Ackerman(4,2) is equal to 42
:)
Herp Derpingson if only, if only...
This is amazing.
I have been in computers and programming a long time, (1972) and this is new ground for me.
Thanks for sharing it.
I love computerphile, wish I found out about them when I was in middle or highschool to explore computer science sooner rather than in college.
example of enumerable recursion with occasional output: "Display all files in drive C"
example of undescidable recursion: "write a text file that contains the hash value of the file when the file is hashed."
I remember when in school we were making the program that solved the “Hanoi tower” problem and then we made a fractal tree that was moving in the wind - it was so beautiful!
Since that day I fell in love with recursions and fractals!
I'm confused, you can simulate a turing machine using for loops and thus can implement ack within that?
Recursively Enumerable includes undecidable problems. The halting problem is undecidable and recursively enumerable (just run the turing machine and accept if it halts). What you meant to put at the end is unrecognizable problems. An example of an unrecognizable problem is all turing machine input pairs that do not halt.
Ooops, I think I just crashed a planetary superbrain in the Perseus arm. by asking it to compute Ack(G, G), where G is Grahams Number.
See the thing is, that's barely bigger than G64 already. It's actually smaller than G65
Ack(G64, G64) looks to be 2 ↑^(G64) (G64 + 3) whereas
G65 = 3 ↑^(G64) G64
↑^(G64) refers to G64 Knuth Arrows
Umbrall
Let's feed it an xkcd number.
Smonjirez G65 has the G64 arrows between two 3s. His number, though, is a lot less than G66.
Cooper Gates That's what I was saying. It's not even just smaller than G66 it's smaller than G65
Umbrall No, he put G64 arrows between G64 twice instead of two 3s, so it is a lot larger than G65.
i believe that for loops and recursion are only needed when working with indexes and such. but not when doing math... there is always an equation. that will do it next to instantly.
steven johnston No. Elementary functions can be defined recursively and there is no closed for solution to them. Some functions are defined as infinite sums of basis functions. Most differential equations have no closed for solutions and must be solved numerically. In all these cases, loops or recursions are absolutely necessary. And it's definitely not true that it can be computed instantly. I currently have 3 computers working for almost a month on one problem ;)
wuuut? i disagree math is all about recursion... the simplest of elements in math revolve around recursion like say counting but before we can count we have to define natural numbers; how do you define a number? well a number is either zero or the increment of a number, so you can practically create a function called "number 5" which is just inc^5(zero), see? recursion
int ack(int m, int n){
if(m==0)return n+1;
if(n==0)return ack(m-1, 1);
return ack(m-1, ack(m,n-1));
}
here's a simple java version for anyone wanting to play with it, overflows pretty easily
At school while learning VB6 long time ago, I made a horse race game project. It had to have random values on the power of the horse but I felt that this PC random function was not enough random to me. So in the race the speed was randomly changing speed by a random factor for a random time. This is how you could have a 200MHz computer completely freeze. At that moment I understood that my code was not optimized.
the time for computation blew my mind as same as the hanoi tower, this is astonishing
The value of each iteration can be figured out using tetration.
2^^x
2
4
16 - 3 = 13
65536 - 3 = 65533
2.00353 × 10^19,728 - 3 = 2.00353 × 10^19,728
and so on
Or im just completely wrong and have no idea what im talking about.
as he said that in the past it took 11 minutes and now he says - 10 years later, we are doing it in 3, so more than 3 times as fast, it will take less than a minute. that is if processing power doesn't have any leap forward.
It's important to point out that this guy is not a software engineer, otherwise he might have known that his code snippet needed indentation, that his computer doesn't have a Pentium, or that Haskell solves practically everything via recursion. Not that it matters, I mean after all he's obviously an expert in computational science.
Ironically using recursion for Ackermann function leads to serious technical problem: stack overflow. So you better convert it to iteration algorithm or reimplement the stack.
Following C program prints all results of Ackermann function where result is within unsigned long int range. No recursion here, but it's very different approach, go through result values and determine what m,n it is an answer for.
#include
#include
#include
#define maxM 100
print_ack(int m, unsigned long int n, unsigned long int v)
{
printf("ack(%d,%ld)=%ld
", m, n, v);
}
main()
{
int i;
unsigned long int val, n[maxM]={0}, v[maxM];
for (i = 1; i < maxM; i++) v[i]=-1;
for (val = 1; val < ULONG_MAX; val++) {
v[0] = val;
print_ack(0, n[0], val);
for(i=0; 1; i++) {
if(n[i]==1) {
v[i+1]=val;
n[i+1]=0;
print_ack(i+1, n[i+1], val);
} else if(n[i]==v[i+1]) {
v[i+1]=val;
n[i+1]+=1;
print_ack(i+1, n[i+1], val);
} else break;
}
n[0]++;
}
}
As written, this program is certainly very long winded to compute. However, from what I can see, it does seem that at least some of its recursive nature can be removed. As written there is only 1 base case solution: Ack(0,n) = n+1, all other cases are defined recursively. However, from observing the results of the function, it appears that you can define some other non-recursive base cases.
For example, Ack(1,n) = n+2. You can check and you'll see that any time the first parameter is 1 then the answer will always be 2 more than the 2nd parameter.
Also, Ack(2,n) = 2n+3, again.
And I'm slightly less confident, but still pretty sure that Ack(3,n) = 2^(n+3) - 3
If you were to implement these additional base cases into the program it would cut out a lot of the recursion required. I would imagine that it's probably possible to devise other base cases for other values of m, but it gets rather difficult due to the sheer growth. It may even be possible that there is a generalization for computing these base cases for any m, which could completely remove recursion (though that would require a far greater mind than my own).
Anyways, assuming that my base case for Ack(3,n) is correct, as well as using previously calculated results, then I've managed to calculate Ack(4,2) in about a matter of seconds.
Ack(4,2) would obviously become Ack(3,Ack(4,1)) -> Ack(3, 65533) and I've proposed a base case for that. So, assuming my base case is accurate, Ack(4,2) = 2^65536 - 3
I easily found an online calculator that could handle such an answer, it happens to be 19,729 digits long, so I can't exactly post it here.
The base case for Ack(4,n) appears to be power-tower related, as the "known" values (including ack4,2) are:
Ack(4,0) = 2^4 - 3
Ack(4,1) = 2^16 - 3
Ack(4,2) = 2^65536 - 3
So I assume that Ack(4,3) must be equal to 2^(2^(65536)) - 3
I tried to calculate this online as well, but couldn't find a calculator that would accept a nearly 19 thousand digit exponent :(
But my point is, is that these values CAN, in fact, be calculated non-recursively.
Oh, you know what, Computerphile? You got this wrong. Right at 5:16, he says "look it gives back an integer result" and you highlighted "int m,n"--that is NOT the line that defines the type of the return value. It is the int before the ack that says the return value will be an integer.
When Prof. Brailsford talks about "derecursing", is he talking about corecursion? Where does duality fit in with each of these classes of problems, primitive recursive, recursive, and recursively enumerable?
I got it! Ackerman (4, 2), put those to numbers together. 42. Therefore, the final result of ackerman (4, 2) will be the answer to life, the universe, and everything, but in a different form. Obviously, it is going to take til the end of the universe for us to find Ackerman (4,2) on a linux machine, we nee something much more powerful like Deep Thought.
With various optimizations in C++ I can get ackermann(4,2) pretty much instantly.
With more optimizations my computer locks up attempting ackermann(4,3). Give it enough stack to not segfault and it just locks the whole thing up. I wasn't expecting my computer to be sufficiently faster than the Professors to actually get a result within my lifetime, but it was a fun attempt.
what's ackermann(4,2)??
@@xynyde0 It's nearly 20,000 digits long and I don't think UA-cam comments allow that many characters.
And whoever thought about stuffing Graham's Number into this formula is an absolute maniac.
Like some Apocalypse Now shit when he starts talking about the recursive part of Ackermann's function.
Surely this could be sped up using dynamic programming... Interesting algorithm, though. Thank you for posting it.
Hmm,those ackermans have evolved...
I solved ack(4, 2). It took my computer quite some time.
2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880933348101038234342907263181822949382118812668869506364761547029165041871916351587966347219442930927982084309104855990570159318959639524863372367203002916969592156108764948889254090805911457037675208500206671563702366126359747144807111774815880914135742720967190151836282560618091458852699826141425030123391108273603843767876449043205960379124490905707560314035076162562476031863793126484703743782954975613770981604614413308692118102485959152380195331030292162800160568670105651646750568038741529463842244845292537361442533614373729088303794601274724958414864915930647252015155693922628180691650796381064132275307267143998158508811292628901134237782705567421080070065283963322155077831214288551675554073345107213112427399562982719769150054883905223804357045848197956393157853510018992000024141963706813559840464039472194016069517690156119726982337890017641517190051133466306898140219383481435426387306539552969691388024158161859561100640362119796101859534802787167200122604642492385111393400464351623867567078745259464670903886547743483217897012764455529409092021959585751622973333576159552394885297579954028471943529913543763705986928913757153740001986394332464890052543106629669165243419174691389632476560289415199775477703138064781342309596190960654591300890188887588084733625956065444888501447335706058817090162108499714529568344061979690565469813631162053579369791403236328496233046421066136200220175787851857409162050489711781820400187282939943446186224328009837323764931814789848119452713007440220765680910376203999203492023906626264491909167985461515778839060397720759279378852241294301017458086862263369284725851403039615558564330385450688652213114813638408384778263790459607186876728509763471271988890680478243230394718650525660978150729861141430305816927924971409161059417185352275887504477592218301158780701975535722241400019548102005661773589781499532325208589753463547007786690406429016763808161740550405117670093673202804549339027992491867306539931640720492238474815280619166900933805732120816350707634351669869625020969023162859350071874190579161241536897514808261904847946571736601005892476655445840838334790544144817684255327207315586349347605137419779525190365032198020108764738368682531025183377533908861426184800374008082238104076468878471647552945326947661700424461063311238021134588694532200116564076327023074292426051582811070387018345324567635625951430032037432740780879056283663406965030844225855967039271869461158513793386475699748568670079823960604393478850861649260304945061743412365828352144806726676841807083754862211408236579802961200027441324438432402331257403545019352428776430880232850855886089962774458164680857875115807014743763867976955049991643998284357290415378143438847303484261903388841494031366139854257635577105335580206622185577060082551288893332226436281984838613239570676191409638533832374343758830859233722284644287996245605476932428998432652677378373173288063210753211238680604674708428051166488709084770291208161104912555598322366244868556651402684641209694982590565519216188104341226838996283071654868525536914850299539675503954938371853405900096187489473992880432496373165753803673586710175783994818471798498246948060532081996066183434012476096639519778021441199752546704080608499344178256285092726523709898651539462193004607364507926212975917698293892367015170992091531567814439791248475706237804600009918293321306880570046591458387208088016887445835557926258465124763087148566313528934166117490617526671492672176128330845273936469244582892571388877839056300482483799839692029222215486145902373478222682521639957440801727144146179559226175083889020074169926238300282286249284182671243405751424188569994272331606998712986882771820617214453142574944015066139463169197629181506579745526236191224848063890033669074365989226349564114665503062965960199720636202603521917776740668777463549375318899587866282125469797102065747232721372918144666659421872003474508942830911535189271114287108376159222380276605327823351661555149369375778466670145717971901227117812780450240026384758788339396817962950690798817121690686929538248529830023476068454114178139110648560236549754227497231007615131870024053910510913817843721791422528587432098524957878034683703337818421444017138688124249984418618129271198533315382567321870421530631197748535214670955334626336610864667332292409879849256691109516143618601548909740241913509623043612196128165950518666022030715613684732364660868905014263913906515063908199378852318365059897299125404479443425166774299659811849233151555272883274028352688442408752811283289980625912673699546247341543333500147231430612750390307397135252069338173843322950701049061867539433130784798015655130384758155685236218010419650255596181934986315913233036096461905990236112681196023441843363334594927631946101716652913823717182394299216272538461776065694542297877071383198817036964588689811863210976900355735884624464835706291453052757101278872027965364479724025405448132748391794128826423835171949197209797145936887537198729130831738033911016128547415377377715951728084111627597186384924222802373441925469991983672192131287035585307966942713416391033882754318613643490100943197409047331014476299861725424423355612237435715825933382804986243892498222780715951762757847109475119033482241412025182688713728193104253478196128440176479531505057110722974314569915223451643121848657575786528197564843508958384722923534559464521215831657751471298708225909292655638836651120681943836904116252668710044560243704200663709001941185557160472044643696932850060046928140507119069261393993902735534545567470314903886022024639948260501762431969305640666366626090207048887438898907498152865444381862917382901051820869936382661868303915273264581286782806601337500096593364625146091723180312930347877421234679118454791311109897794648216922505629399956793483801699157439700537542134485874586856047286751065423341893839099110586465595113646061055156838541217459801807133163612573079611168343863767667307354583494789788316330129240800836356825939157113130978030516441716682518346573675934198084958947940983292500086389778563494693212473426103062713745077286156922596628573857905533240641849018451328284632709269753830867308409142247659474439973348130810986399417379789657010687026734161967196591599588537834822988270125605842365589539690306474965584147981310997157542043256395776070485100881578291408250777738559790129129407309462785944505859412273194812753225152324801503466519048228961406646890305102510916237770448486230229488966711380555607956620732449373374027836767300203011615227008921843515652121379215748206859356920790214502277133099987729459596952817044582181956080965811702798062669891205061560742325686842271306295009864421853470810407128917646906550836129916694778023822502789667843489199409657361704586786242554006942516693979292624714524945408858422726153755260071904336329196375777502176005195800693847635789586878489536872122898557806826518192703632099480155874455575175312736471421295536494084385586615208012115079075068553344489258693283859653013272046970694571546959353658571788894862333292465202735853188533370948455403336565356988172582528918056635488363743793348411845580168331827676834646291995605513470039147876808640322629616641560667508153710646723108461964247537490553744805318226002710216400980584497526023035640038083472053149941172965736785066421400842696497103241919182121213206939769143923368374709228267738708132236680086924703491586840991153098315412063566123187504305467536983230827966457417620806593177265685841681837966106144963432544111706941700222657817358351259821080769101961052229263879745049019254311900620561906577452416191913187533984049343976823310298465893318373015809592522829206820862230332585280119266496314441316442773003237792274712330696417149945532261035475145631290668854345426869788447742981777493710117614651624183616680254815296335308490849943006763654806102940094693750609845588558043970485914449584445079978497045583550685408745163316464118083123079704389849190506587586425810738422420591191941674182490452700288263983057950057341711487031187142834184499153456702915280104485145176055306971441761368582384102787659324662689978418319620312262421177391477208004883578333569204533935953254564897028558589735505751235129536540502842081022785248776603574246366673148680279486052445782673626230852978265057114624846595914210278122788941448163994973881884622768244851622051817076722169863265701654316919742651230041757329904473537672536845792754365412826553581858046840069367718605020070547247548400805530424951854495267247261347318174742180078574693465447136036975884118029408039616746946288540679172138601225419503819704538417268006398820656328792839582708510919958839448297775647152026132871089526163417707151642899487953564854553553148754978134009964854498635824847690590033116961303766127923464323129706628411307427046202032013368350385425360313636763575212604707425311209233402837482949453104727418969287275572027615272268283376741393425652653283068469997597097750005560889932685025049212884068274139881631540456490350775871680074055685724021758685439053228133770707415830756269628316955687424060527726485853050611356384851965918968649596335568216975437621430778665934730450164822432964891270709898076676625671517269062058815549666382573829274182082278960684488222983394816670984039024283514306813767253460126007269262969468672750794346190439996618979611928750519442356402644303271737341591281496056168353988188569484045342311424613559925272330064881627466723523751234311893442118885085079358163848994487544756331689213869675574302737953785262542329024881047181939037220666894702204258836895840939998453560948869946833852579675161882159410981624918741813364726965123980677561947912557957446471427868624053750576104204267149366084980238274680575982591331006919941904651906531171908926077949119217946407355129633864523035673345588033313197080365457184791550432654899559705862888286866606618021882248602144999973122164138170653480175510438406624412822803616648904257377640956326482825258407669045608439490325290526337532316509087681336614242398309530806549661879381949120033919489494065132398816642080088395554942237096734840072642705701165089075196155370186264797456381187856175457113400473810762763014953309735174180655479112660938034311378532532883533352024934365979129341284854970946826329075830193072665337782559314331110963848053940859283988907796210479847919686876539987477095912788727475874439806779824968278272200926449944559380414608770641941810440758269805688038949654616587983904660587645341810289907194293021774519976104495043196841503455514044820928933378657363052830619990077748726922998608279053171691876578860908941817057993404890218441559791092676862796597583952483926734883634745651687016166240642424241228961118010615682342539392180052483454723779219911228595914191877491793823340010078128326506710281781396029120914720100947878752551263372884222353869490067927664511634758101193875319657242121476038284774774571704578610417385747911301908583877890152334343013005282797038580359815182929600305682612091950943737325454171056383887047528950563961029843641360935641632589408137981511693338619797339821670761004607980096016024823096943043806956620123213650140549586250615282588033022908385812478469315720323233601899469437647726721879376826431828382603564520699468630216048874528424363593558622333506235945002890558581611275341783750455936126130852640828051213873177490200249552738734585956405160830583053770732533971552620444705429573538361113677523169972740292941674204423248113875075631319078272188864053374694213842169928862940479635305150560788126366206497231257579019598873041195626227343728900516561111094111745277965482790471250581999077498063821559376885546498822938985408291325129076478386322494781016753491693489288104203015610283386143827378160946341335383578340765314321417150655877547820252454780657301342277470616744241968952613164274104695474621483756288299771804186785084546965619150908695874251184435837306590951460980451247409411373899927822492983367796011015387096129749705566301637307202750734759922943792393824427421186158236161317886392553095117188421298508307238259729144142251579403883011359083331651858234967221259621812507058113759495525022747274674369887131926670769299199084467161228738858457584622726573330753735572823951616964175198675012681745429323738294143824814377139861906716657572945807804820559511881687188075212971832636442155336787751274766940790117057509819575084563565217389544179875074523854455200133572033332379895074393905312918212255259833790909463630202185353848854825062897715616963860712382771725621313460549401770413581731931763370136332252819127547191443450920711848838366818174263342949611870091503049165339464763717766439120798347494627397822171502090670190302469762151278521956142070806461631373236517853976292092025500288962012970141379640038055734949269073535145961208674796547733692958773628635660143767964038430796864138563447801328261284589184898528048048844180821639423974014362903481665458114454366460032490618763039502356402044530748210241366895196644221339200757479128683805175150634662569391937740283512075666260829890491877287833852178522792045771846965855278790447562192663992008409302075673925363735628390829817577902153202106409617373283598494066652141198183810884515459772895164572131897797907491941013148368544639616904607030107596818933741217575988165127000761262789169510406315857637534787420070222051070891257612361658026806815858499852631465878086616800733264676830206391697203064894405628195406190685242003053463156621891327309069687353181641094514288036605995220248248886711554429104721929134248346438705368508648749099178812670565665387191049721820042371492740164460943459845392536706132210616533085662021188968234005752675486101476993688738209584552211571923479686888160853631615862880150395949418529489227074410828207169303387818084936204018255222271010985653444817207470756019245915599431072949578197878590578940052540122867517142511184356437184053563024181225473266093302710397968091064939272722683035410467632591355279683837705019855234621222858410557119921731717969804339317707750755627056047831779844447637560254637033369247114220815519973691371975163241302748712199863404548248524570118553342675264715978310731245663429805221455494156252724028915333354349341217862037007260315279870771872491234494477147909520734761385425485311552773301030342476835865496093722324007154518129732692081058424090557725645803681462234493189708138897143299831347617799679712453782310703739151473878692119187566700319321281896803322696594459286210607438827416919465162267632540665070881071030394178860564893769816734159025925194611823642945652669372203155504700213598846292758012527715422016629954863130324912311029627923723899766416803497141226527931907636326136814145516376656559839788489381733082668779901962886932296597379951931621187215455287394170243669885593888793316744533363119541518404088283815193421234122820030950313341050704760159987985472529190665222479319715440331794836837373220821885773341623856441380700541913530245943913502554531886454796252260251762928374330465102361057583514550739443339610216229675461415781127197001738611494279501411253280621254775810512972088465263158094806633687670147310733540717710876615935856814098212967730759197382973441445256688770855324570888958320993823432102718224114763732791357568615421252849657903335093152776925505845644010552192644505312073756287744998163646332835816140330175813967359427327690448920361880386754955751806890058532927201493923500525845146706982628548257883267398735220457228239290207144822219885587102896991935873074277815159757620764023951243860202032596596250212578349957710085626386118233813318509014686577064010676278617583772772895892746039403930337271873850536912957126715066896688493880885142943609962012966759079225082275313812849851526902931700263136328942095797577959327635531162066753488651317323872438748063513314512644889967589828812925480076425186586490241111127301357197181381602583178506932244007998656635371544088454866393181708395735780799059730839094881804060935959190907473960904410150516321749681412100765719177483767355751000733616922386537429079457803200042337452807566153042929014495780629634138383551783599764708851349004856973697965238695845994595592090709058956891451141412684505462117945026611750166928260250950770778211950432617383223562437601776799362796099368975191394965033358507155418436456852616674243688920371037495328425927131610537834980740739158633817967658425258036737206469351248652238481341663808061505704829059890696451936440018597120425723007316410009916987524260377362177763430621616744884930810929901009517974541564251204822086714586849255132444266777127863728211331536224301091824391243380214046242223349153559516890816288487989988273630445372432174280215755777967021666317047969728172483392841015642274507271779269399929740308072770395013581545142494049026536105825409373114653104943382484379718606937214444600826798002471229489405761853892203425608302697052876621377373594394224114707074072902725461307358541745691419446487624357682397065703184168467540733466346293673983620004041400714054277632480132742202685393698869787607009590048684650626771363070979821006557285101306601010780633743344773073478653881742681230743766066643312775356466578603715192922768440458273283243808212841218776132042460464900801054731426749260826922155637405486241717031027919996942645620955619816454547662045022411449404749349832206807191352767986747813458203859570413466177937228534940031631599544093684089572533438702986717829770373332806801764639502090023941931499115009105276821119510999063166150311585582835582607179410052528583611369961303442790173811787412061288182062023263849861515656451230047792967563618345768105043341769543067538041113928553792529241347339481050532025708728186307291158911335942014761872664291564036371927602306283840650425441742335464549987055318726887926424102147363698625463747159744354943443899730051742525110877357886390946812096673428152585919924857640488055071329814299359911463239919113959926752576359007446572810191805841807342227734721397723218231771716916400108826112549093361186780575722391018186168549108500885272274374212086524852372456248697662245384819298671129452945515497030585919307198497105414181636968976131126744027009648667545934567059936995464500558921628047976365686133316563907395703272034389175415267500915011198856872708848195531676931681272892143031376818016445477367518353497857924276463354162433601125960252109501612264110346083465648235597934274056868849224458745493776752120324703803035491157544831295275891939893680876327685438769557694881422844311998595700727521393176837831770339130423060958999137314684569010422095161967070506420256733873446115655276175992727151877660010238944760539789516945708802728736225121076224091810066700883474737605156285533943565843756271241244457651663064085939507947550920463932245202535463634444791755661725962187199279186575490857852950012840229035061514937310107009446151011613712423761426722541732055959202782129325725947146417224977321316381845326555279604270541871496236585252458648933254145062642337885651464670604298564781968461593663288954299780722542264790400616019751975007460545150060291806638271497016110987951336633771378434416194053121445291855180136575558667615019373029691932076120009255065081583275508499340768797252369987023567931026804136745718956641431852679054717169962990363015545645090044802789055701968328313630718997699153166679208958768572290600915472919636381673596673959975710326015571920237348580521128117458610065152598883843114511894880552129145775699146577530041384717124577965048175856395072895337539755822087777506072339445587895905719156733
I did it mathematically and got the same answer: 2**(65533+3)-3
Actually I tweaked the algorithm to get rid of some recursions, to be able to calculate this quicker.
if m == 0: ans = n + 1
elif m == 1: ans = n + 2
elif m == 2: ans = 2 * n + 3
elif m == 3: ans = 2 ** (n + 3) - 3
elif n == 0: ans = ack(m - 1, 1)
else: ans = ack(m - 1, ack(m, n - 1))
I wanted to continue to m == 4, but seeing that number I lost the will to continue.
My nightmare is that the program that I wrote and ran as a teeanger will overlive me
Matter is the opposing way of random with multiples. Those types together creates existence, logically! Possibly our existence!
Fantastic video. Professor Brailsford is awesome. ❤
While I agree this is a difficult computable functions, I would think the most difficult programs to compute are the ones which we cannot.
My linux box with default stack overflowed the stack before getting ackermann(4,1) of course there is no check for stack exhaustion, so absent any checking it blithely continues and computes it.
Use "-Wl,-stack,", on the gcc command line, to increase the stack size.
Great video! N and M are terrible variable names though because they both sound the same in English
the Halting problem. First known in math, then logic, almost at the same time, then computer science (Turing).
Why do you keep saying that "some problems HAVE to be done recursively"?.. any problem can be implemented with for/while loops because recursion is based on the stack and you can build your own stack with iterrative code. I can write you a pretty easy code in C/C++ that computes ackermann without using recursion.
A program that maintains its own stack is doing recursion.
Is this something quantum computing could figure out?
Only if you have enough computing elements to store the answer, which in this case would take up more space than the universe even if it were as dense as a singularity...
Teth47 65536 bits isn't that difficult to get, is it?
possible
Teth47 a black hole has infinite density.
every single number you could think of will fit in there.
Blox117 No, but even if it did, that's not what that means...
Also black hole != singularity...
Can we please run the Ackermann program on a supercomputer and hopefully get it down to a couple of decades? I just want to know what the answer is!
At the end of the Three Body Problem, with the Universe collapsing into two dimensionality and people coming out of their pocket universes to contribute critical matter to aid it's rebirth, I bet out of camera shot there is someone at an intergalactic mainframe terminal who just got the answer to this and is hoping they can skim-read the 20000 decimal places before the big crunch happens just to say "we did it, I saw the answer!"
by the way, really interesting, would love a video about dynamic programming by prof Brailsford
2^65533 is Brailsford's Number.
I implemented memoization, but due to limits with the stack I still cant compute (4,2). but (4,1) was instant, I also got up to (3, 21) : 16,777,213
With memoization, I figured out that to compute (m,n+1), it is double the operations it takes for (m,n)
Nice I am gonna try on the supercomputer when I get the money.
Or I will just ask bill gates for a small loan.
You can speed things up considerably if you relax the condition of correctness.
Why are so many of those ackerman results a power of two, minus three?
It holds continuously from (2,5) to (4,1) ... and with that stunning 65,533 on the end :O
I realize this video is nearly 4 years old and the chances of comments not seen are great, but does anyone know about how the code was compiled and run? I wrote an ANSI C version of the code shown on an Ubuntu machine and within minutes it returns a segmentation fault when computing 4,2, let alone running it for how long is claimed in the video. This was compiled with gcc, but with all default values.
cool video. but the big crunch will never happen; dark energy forces the universe to expand infinitely and exponentially. Unless the big rip occurs, your computer can finish the computation as long as it has power. Luckily, the infinite expansion is called "heat death", so the computer will become progressively colder, and the maximum speed and energy efficiency increase as the temperature drops. How long it can actually go on is related to the rate of temperature drop in proportion to the efficiency gain. I'm sure the calculation is tractable, but I'm not quite curious enough to do it.
On your previous video I played with factorials (in Visual Basic) doing this :
Dim n As Integer = factorial(n)
Or for all those C/C++ coders it translate :
int n = factorial(n); (not sure in C/C++ it will compile, too lazy to try it on C)
Of course I got overflow and it crash, but what about :
ackermann(ackermann(ackermann, ackermann), ackermann(ackermann, ackermann)) ? :D
Or even worst :
ackermann(ackermann(ackermann(rnd), ackermann(rnd)), ackermann(ackermann(rnd), ackermann(rnd)))
You are sure the first will never end and will goes on for ever trying to find out what he is himself (if it compile)
But the second with (rnd) for random might reach a ridiculous proportion before you even realise it :D
Edit :
Ho and technically I can make it non recursive, I've done an experiment and write a Quick Sort and a Merge Sort algorithm the same way they should work recursively but using an array (that does the same job as the stack) and it can goes on until it finish using a "for loop", the only limit is the overflow with the array size, but if you can you can use multiple array, array_n(address) that when a first one get too large lets say array_0(maxaddress), you switch to array_1(0) and so one, which will lead to being able to do the equivalent of recursion inside recursion using an iterative program with only limit your memory (and even here you can write files and free some array to use your whole HDD to have even more false recursion going on) !
i don't alwys use recursion...but when i use recursion i don't always use recursion.
to understand recursion, you must first understand recursion
@@RKBock to write a recursive function you must first write a recursive function to write a recursive function
@@shadowagent3 To write a recursive comment some one else must add up the next recursive comment
holds beer
the only way to understand recursive function is to do it recursively
Absolutely fascinating. I can only imagine how much more fascinating it would be if i knew what he was talking about.
basically it's interesting if you like studying theoretical software. It's some interesting concepts, but it's utterly useless for actually writing software. This would do essentially the same thing:
#include
.
.
.
double time;
increase(time, time);
sleep( time );
.
.
.
double increase( double time, double temp_time)
{
time = pow(2, increase(time, temp_time-1);
return time;
}
it's clunky but I'm not going to bother optimizeing and cleaning it up. it basically sleeps for 2^time!, or two raised to time factorial.
Edit: at least as far as wasting cycles it would behave simularly
lol, same
Christian Herrera
So I'm not alone
yes! loved it though
Low key just copied and pasted this into an ide I’m in CS1 , but changing my degree plan after this semester
Ack(-1, -1); ... The thread running this code has never been seen again.
Herp Derpington
haha, yeah gotta add error checking in there
...
#include
...
assert (m >= 0 && n >= 0);
...
lukitree don't use tho, use
Herp Derpington Define the int's as uint and it'll protect you from this nonsense. :P
+Herp Derpington
Actually, I still think it would terminate, because once m and n get small enough, the sign bit will flip and suddenly we're back at a positive number.
Nah, it just produces StackOverflowError.
I checked the size of 3 * 2 ** 65333 in python
the number itself is 280 lines in windows powershell
And it probably just filled the final lines with a bunch of zeroes because it cannot compute that large an integer.
@@EmptyKingdoms Python can
@@dramforever using what tools?
@@EmptyKingdoms For the purpose of explaining, consider this: In principle, you can represent a large number by its digits, and turn the multiplication with pencil and paper method ('schoolbook multiplication') into a program. It can handle anything that your computer can store. (280 lines of characters is like *nothing* compared to GBs of RAM) It won't be fast, but it shouldn't be too slow either. Now you can just start from 3 and keep multiplying by 2, which is again slow but shouldn't be unbearable. (You can even specialize and just write a 'multiply by single digit number' function) There are faster ways to do multiplication (google 'integer multiplication algorithm'), and also for exponentiation, but I'm not really familiar with those, but they are pretty well researched by others so maybe just consult what others already wrote.
But actually, big integer implementations, or arbitrary precision integer implementations (look ma, no precision loss for final digits) use binary internally (bytes and words are just chunks of binary bits). 3 * 2**65533 is really neat in binary, so the real deal is converting it to decimal. Again, someone else already figured it out like ages ago. Just google 'radix conversion algorithm'.
But why computers sometimes can't handle large numbers? Because really they just can't handle them *fast*. Like *real* fast. Your CPU has dedicated *hardware* circuitry to handle not too large integers and not too wild floats, so that if your program does not need 'weird' computation like computing a very large number it ends up blazingly fast, and most programs actually do just need normal numbers.
@@dramforever thank you.
It'd be funny if the program returned -1/12.
unfortunately it has to be an integer and -1/12 is not so something would've gone wrong, but I do like your thinking though.
Minox sta
Some would argue that summing natural integers to infinity would be integer as well... : ua-cam.com/video/w-I6XTVZXww/v-deo.html
Minox sta summing positive integers is not supposed to be negative. But 1 + 2 + 3 + 4 + 5 + ... = -1/12 (see numberphile)
So if string theory can incorporate that, why not ?
You only get -1/12 if you go all the way to infinity.
Whatever stupendous number it puts out will be just as far from infinity as 1.
Minox sta But adding all the natural numbers must be an integer, right?
Ah, nothing like theoretical computer science.
"and within that VILE second argument.."
This is too funny! I like this guy.
g64 is graham's number (see one of Brady's other videos). I first saw Ack(g64, g64) in an xkcd comic though. So you're looking at a number created through superexponential means, fed into a function that has a super exponential time complexity.
Graham's number is insane. But the most amazing thing is that the only thing bigger than Graham's Number ... is yo momma XD
Thats gonna be fun :D
It will stop calculating even before you really startet the ackerman part...
Krisna Siv Nope, there's a thread on the xkcd forums called "My Number is Bigger!", they've found numbers that make my mother look negligible.
What about Ack(TREE(g64),TREE(g64))
Sir, thank you for this. From app engineers to web developers, I’ve always felt that it is vitally important for programmers to study the mathematical properties that make our projects work. To do otherwise, to me, is like trying to be a materials engineer without having an understanding of the physical and chemical properties of your raw materials.
the result will probably be 42
Jerónimo Barraco Mármol
ack(ack(life, universe),ack(everything, douglasadams))
+Jerónimo Barraco Mármol
A distinct possibility. What was the question?
+Dan Overlin To know the question we would need a computer and an algorithm far more complicated. It would probably take ten million years to know.
Another 5 minutes and we would have had the answer . . . damn the Vagons! The best laid plans of mice . . .
I would give you an upvote but you are already at 42 and I would hate to ruin that.
9:45
I reproduced the function in Python and believe I got it right as it gives me the same results, except for ack(4, 1): _"RecursionError: maximum recursion depth exceeded while calling a Python object"_
lulz at Python
Python, please.
use like Java, c#, c++, etc
You can change the recursion limit in Python.
Thanks for the replies. I guess I should have known, I'm still pretty wet behind the ears when it comes to programming.
+Raimund yes but how?
I want Professor Brailsford as my lecturer. He's awesome :D
Suave Atore wait is that his name? THATS SUCH A COOL NAME
You know you're a true mathematician when you get scared by how big a number can get.
Also makes you appreciate how big infinity actually is. It's bigger than any ack out there.
any ack out there is finite, regardless of how big it is. Infinity on the other hand literally means not finite.
Well, infinity isn’t bigger than any number. Infinity is an undefined value, so it cannot be compared to numbers. For example, you may be tempted to say that 1/0 is infinity because division by a value extremely close to zero results in an extremely huge number, but it’s technically undefined. The reason why it’s crazy to try to comprehend the “hugeness” of infinity is only because that for any number you come up with, you can always add one to it (or do some crazy operation) and it’s even bigger. It goes from incomprehensible to even more incomprehensible. Just wanted to say that infinity isn’t comparable to numbers, but more just an undefined thing that *does not exist in the set of real numbers.*
(That’s an obvious fact, but with that in mind, it should also be obvious that saying infinity is bigger than a number is just as senseless as saying infinity is smaller than a number, because they’re apples and oranges.)
Moreover, since 1/x has the limit of “positive” and “negative” infinity as x approaches zero from the right and left side respectively, that should clearly indicate that there is only one infinity, and that is the state of being undefined, not existing within the set of real numbers. When 1/x shoots down toward “negative” infinity from the left and comes back down from “positive” infinity after x passes through zero, that’s the function 1/x escaping the set of real numbers to a single place, called undefined, and returning to the set of real numbers in the same direction in which it exited.
That said, infinity seems like it exists on either “end” of the real number line, so that would mean it’s just as correct to say that infinity is smaller than every single number you can think of. But if that was true, then it’s a contradiction. Infinity cannot be both bigger than and smaller than every real number, and hence it does not exist on either end of the real number line. The existence of infinity is entirely outside of the set of real numbers.
So, finally, infinity cannot be compared to real numbers. It’s not bigger than any ack out there. It’s just that you can construct a number arbitrarily large enough to be bigger than any ack out there, and that’s what is mind-boggling. :)
“It’s longer than you think, dad!”
All the cores in the world won't help you since this C code will run in a single thread. Also the first thing I thought was "wouldn't memoisation help improve performance?"
After a quick google search, I discovered that "When a software developer learns about the Ackermann function, he will try to see how much of improvement function memoisation does if any". LOL
How much is it?
HebaruSan probably at least some, if any
Funnily true ...
can confirm lol
After breaking various online 'big number calculators' I found one that works, and it turns out 2^65533 * 3 minutes rounds out to, unless I've screwed up somewhere, about 1x10^19712 times the age of the universe. Not terribly helpful.
(((((2^65533 * 3) / 60) / 24) / 365) / 13700000000) = 1.0434008320186794 × 10^19712
If you want help with big powers like that, try making logarithms of everything; multiplying and dividing stuff like that turns into adding and subtracting more manageable numbers.
You could try writing a memoized version of this code, where it remembers the result of a previous computation, and just plops that result in so it won't have to spend time working that out, cuz it seems to me that that's what's slowing it down so much; that it has to go through the same set of computations again and again
EDIT: PEOPLE before commenting on why it wouldn't work; please read the other comments! THEY MAY ALREADY HAVE COME TO THE SAME CONCLUSION! Please don't waste precious keystrokes on repeated information, thank you
But I wanted to know why they didn't, and the comments you refer to aren't on the first page anymore D:
This i called "Dynamic programming" :)
Yuriy Grinevich do your research, memoization has its differences
Yuriy Grinevich Memoization is a technique that can be involved in dynamic programming.
Nikolaj Lepka As far as I know your approach is known as " backtracking " , so for the people saying it wont work , it will. It will indeed make it faster.
ack(tree(3), graham's number)
7
The salad is strong in this one.
You are already at the magnitude of TREE(3), doing an ackermann function (which is EXTREMELY weak by comparison) won't really do anything.
42
The TREE function is way stronger than the Ackermann function. However, the follow-up video of this video was about a function even stronger than the TREE function - the Busy Beaver function.
this dude's voice is absolutely soothing.
Hi Professor Brailsford! I've really enjoyed all your videos, thank you for taking the time to make them. It has been a couple years for me since graduating, and I miss my senior level computer science classes. Your lectures remind me of why I got in to and love the field... and not for a day job
It seems that some reductions can be made in the levels of recursion by adding cases for the following:
ack(1, n) = n + 2
ack(2, n) = 2*n + 3
ack(3, n) = 1
Yeah, that’s one way to improve it.
Another optimization is to convert one of the tail-calls into a loop, that leaves us with just 1 recursive call.
But thanks to your comment I realized there's a simpler way to optimize the A function, define it in terms of a single Hyper-Operation call:
A(m, n) = HyperOP(m, 2, n + 3) - 3
Where the 0th argument of HP is the degree or "order" of the HyperOP we want to use, 1st arg is what we want to hyper-operate, and 2nd arg is the number of times to apply the "sub-HP".
To implement HP efficiently, define it like so:
HP(0, a, b) = b++ //add 1
HP(1, a, b) = a + b
HP(2, a, b) = a × b
HP(3, a, b) = a ^ b //a ** b
The general case HP(n, a, b) requires recursion, it can be an implicit or explicit stack. It's essentially HP(n - 1, a, HP(n - 1, a, ...)), with b copies of HP calls, IIRC.
HP(4, a, b) is tetration, HP(5, a, b) is pentation, etc...
Before I realized this optimization, I just used the Wikipedia table with all closed-form expressions that didn't require recursion, and used a memoization hash table when recursion was needed. After implementing the HP optimization I realized Wikipedia already mentioned that in the "Definition" section, but I didn't understand the notation before... *bruh*
try 4,4
His computer's a bit slow. I compiled his function pretty much verbatim, and it calculates ack(4,1) in 27 seconds. With optimized compilation, it only takes 5.7 seconds.
I don't think I'll bother calculating ack(4,2) though...
***** suggest you watch the follow-on video :) >Sean
***** Ah. That explains it!
+DaKnOb That is true. I had a StackOverflow on 4,1
+Giora Guttsait Try with any functional PL (supports tail call optimization)
+moveaxebx The Ackermann function is not tail recursive. That is essentially what the professor is explaining. Tail call optimization is, in a sense, converting a recursion into a for loop (making it iterative), and you can not do this for functions like ack.
I love listening to Professor Brailsford because it makes me realise, that I'm not that smart and there are so many more interesting things to learn.
Ermagherd that lack of indentation is driving me crazy!!
Agreed. That code would be sooo much easier to read if it were indented! This is like...Computers 101 stuff! ^^;
@@eliatarasoff5872 ermagherd someone learned with python didnt they
Sorry guys I tried :C but I could not do it:
Unhandled System.StackOverflowException.
Do it in python
@@rahulbansode1537 no. python is way to slow for this kind of tasks, because it's interpreted
Obviously. Your stack is way too small to do so many nested stuff
This video taught me how to crash a C++ compiler!
template
struct Ack {
static constexpr size_t value = Ack::value;
};
template
struct Ack {
static constexpr size_t value = Ack::value;
};
template
struct Ack {
static constexpr size_t value = n + 1;
};
template
struct Ack {
static constexpr size_t value = 1;
};
It reminds me "arrow arrow arrow" from Grahams Number LOL
It should. You need Knuth's arrow notation to describe A(4,2).
I downloaded the program files and ran ack(6,6) on my quad core 3.2 ghz machine running Arch Linux. It used 100% of one of my cores, took 1 minute 45 seconds, and ended in a segmentation fault. ack(4,4) also segfaults. ack(3,3) returns in under a second.
Man I sure love Professor Brailsford, I hang on every word he says. Such a great lecturing voice! Such a wise old wizard.
I love this guy
Can a quantum computer be programmed to calculate ackerman function and how many qubits will be needed for that?..
I don't actually know but I'd be really surprised if there was an asymptotically faster quantum algorithm to compute the Ackermann function.
That's not what a quantum computer does. It can only calculates combinations.
Joseph Harrietha Since the Ackermann function is a classic in theoretical computer science, QC being only theoretical at the time being shouldn't matter all that much for the question at hand ;)
From my understanding of QM computing it will give you a possible answer and you'd still have to check its validity. So... no
It's all I gathered from my degree :/
QM computers are much better suited to other types of problems.
Maybe find out if N=NP and all that ha!
g64 is grahams number (MUUUCH bigger than a googleplex). see numberphiles video:
Graham's Number - Numberphile
TREE(3)
Counted the number of recursions required to calculate ack(4, 1) and the result was 2, 862, 984, 010. Mind boggling...
Y2K38 How do you calculate that? Is that its own recursive function?
In the recursive function create a static variable and increase every time for a recursive call
abhineet singh Makes sense.
Would caching make this function more computable? By remembering old results you do not need to recalculate them. Since it only calls the function with reduced arguments, it doesn't seem that hard to build your way up?
I am probably missing something :P
ack(4,2) will access ack(3, 65k), value that was never computed before, which itself will access ack(2, insanely_large_value), and so on.
Nope . Thats memorization for recursion . That's not the problem in this case
ur onto something
I've been jobbing business focused programmer for over thirty years. I was at college recursion was kind of worshiped by my tutors 'oh look at the elegant code' they would say. When I got in to the business world the number of times recursion was the best solution was about twice in thirty years!
Brilliant...!
u guys never sorted anything? i would assume most sort functions are recursive (of course i could be totally wrong - but then again i could be totally right!)? Or do you mean you never had to write any recursive code?
Strangely no because whenever I've had data it's been inside a database, so you get the database to sort the data before you get the data out. Or if you get it into a webpage then use methods from a library like jQuery datatables to handle the sorting for you. I've never needed to get my hands dirty sorting. Infact I remeber doing all that sorting stuff at college level and pretty much never having to use it like I never used truth tables or Karnough maps!
Steve Gould haha yeah - it's the curse (?) of software engineering, learn the nuts and bolts but unless you plan to be an expert on, say sorting, you are better off using someone else's sorting routines - so why learn the nuts and bolts in the 1st place. My answer would be: for job interviews! lol!
cheers!
Spot on DjDedan and in fact some the most successful 'programmers' I know hardly write a line of code. They are just very good a cobbling together solutions from other people's work.
It's been 15 years I'm working professionally in computer science, writing code and doing something useful with it, thinking that I'm kind of understanding how it all works, from the theory of electronics, to the end user using it, I'm mind blown that some mathematician from the early 20s have already thought of all of this. Plus kudos to mr Brallsford explaining it like it's some basic course by its concise explaination. Love from France
Now, here is the nasty thing. You can program Ackermann's function iteratively. It requires setting up a stack and it is not a pretty picture. But you can do it. Those of you aware that no machine language actually has any recursion in it could probably guess this fact.
That's not the point. The point is you can't convert a general recursive function into a FOR loop. Of course, you can convert it into a while loop. You just can not know maximum possible iterations. That's why you can't do a for loop.
Also, machine languages has recursion in it. Recursion basically means calling the currently executing subroutine. What prevents you from doing it? For example, in x86 assembly, you can just use the call instruction.
@@aim2986
Yes you can use the call instruction. But it is not innately recursive, as you will find out when you mess up your stack. It is an iterative instruction. It saves some data to memory, updates a general purpose register and updates the instruction pointer. I stand by my statement. No machine language _actually_ has recursion in it. It has tools you can use to implement recursive algorithms.
@@PvblivsAelivs by that logic no machine language actually has functions in it, too. We can think all non-recursive functions like loops which iterate only once. Like a do..while(false) loop.
@@aim2986
That's true. No machine language actually has functions in it. They are a useful abstraction. But it is not what the processor does.
@@PvblivsAelivs ok. I got you. Machine languages doesn't have functions. But I think assembly languages does. I know that's not the point here, but I just wanted to make it clear. Because you know, we can define labels which we can jump later.
Would ack(m-1,ack(m-1,ack(m,n-1))) still be superexponential or would it have an even bigger growth?
I think there is a rule. Results after ack(3,0) are always (as far as I know) powers of 2 minus 3.
Is there a PROVED rule?
I don't know. That's cool that they are powers of 2 minus 3! 👍 I like powers of 2. The Ack(4,1) value of 65,533 is 3 less than 2^16. 😀 These are amazing and intriguing things on this video!
The piece of code shown is K&R c code style (not ANSI c).
stackoverflow.com/a/1630645/4824854
Please, don't show it on UA-cam, people will code badly.
Thanks for everything else.
You've discussed algorithms that are necessarily recursive. Given that multi-cores and threads are now mainstream, I wonder if there are any algorithms that are necessarily parallel.
+aMulliganStew No, you can always serialize it by interleaving instructions from different threads.
+Jiří Havel That's still parallelization.
Jonathan Park
I meant that you can always emulate a parallel machine on a serial one. This means that there are no problems that are solvable by parallel but not by serial one.
Unless you're executing the threads in a serial manner, that's still parallelization.
Jonathan Park
You can call it this way. I answered to "I wonder if there are any algorithms that are necessarily parallel." And since you can convert any parallel algorithm to a serial one (even if that means emulating some parallel machine), then parallel algorithms can't solve any problem that a serial algorithm can't.
I worked out the fast Ackermann function :)
function fAck(m,n){
var ack = [4,5,6,2,3,4,5,6,7,3,5,7,9,11,13,5,13,29,61,125,253,13,65533];
console.log( ack[m] )
if( m
kowdermeister So that will throw the error every time it's called he he (original call)
Dear mr Professor Brailsford:
1 please use proper indentation (tabs?)
2 is that pre-ansi C (K&R C style?)
I enjoyed watching your video however
I have a different idea--what if we remembered the results of every call, so we could look them up in a table rather than recalculating? Would that simplify the problem? Somewhat at least. We are calling ack with the same values over and over. But is it enough?
Interesting. By remembering the previous values, my program is able to calculate ack(4,1) instantaneously as 65,533. So remembering the previous values does simplify the problem, but I still get a stack error before I get to ack(4,2).
Here's a question. Since there is an obvious pattern to the answers, what if we just rewrite ack to return the value? Is that possible? Or is recursion still necessary in order to calculate the n^n . . . ^n . . . ^n?
Yeah I was thinking of turning this into a math problem to look for shortcuts for 10,10. Maybe if they understood the math it can be written easier. Then you only have a fraction of the work to do.
As this problem is computable via µ-recursion, it is also computable by while-loops, this may speed your calculation up. For the problem of n^n^...^n^n (a power-tower) this can actualy be done with for-loops or primitive recursion, so the computational time is not that bad:
In Python:
def pt(x, y):
n = x
for i in range(y):
n = x ** n
return n
The main problem here is that the numbers also become quite huge and may not fit into memory.
Nothing will help speed up the computation, the simple fact of reading and adding two intermediate values take too long.
Computerphile is such a wonderful treat for me, thank you so much Brady and all of your interviewees for the time and effort putting this together (numberphile as well!). You are doing a service to all mankind, you deserve a trophy!
Wow, that code looked horrible. No indentations or anything at all
Yes, the formatting is perhaps the worst I've seen for a C program. At first I didn't even recognise it as C.
It's an ancient standard of C
Dont you wake up one day and say: "Shit, i need to do some math"
Because i sure thing do
Ackermann was clearly a very naughty boy. The man's created a monstrosity. Imagine feeding it into the Krell Machine and saying, "chew on that, motherflocker!" as the core starts to overheat with Robbie in the background chiming, "warning, warning, what you have done is wrong" and the Id becomes furious and is going to have you!
Ackermann's function is so meta --__--
one question about this: when I wrote this in python I got an error that more than 1000 recursive calls is not possible. While this might be different in other programming languages I'm a bit baffled that this can run for four weeks on their computer and not lead to some memory problem... Cause isn't the thing about recursiveness that we need absurd amounts of memory?
+Ezechielpitau I think you can override this python recursive call barrier somehow.
+Ezechielpitau
> " isn't the thing about recursiveness that we need absurd amounts of memory?"
Tail-call optimization completely eliminates the memory problem, if the programmer makes an effort to lay out the function in a certain way.
+Paulina Jonušaitė ah ok thx, I'll have a look into how that works :)
+Paulina Jonušaitė I believe that will only work for primitive recursive functions. In this case, one branch has a recursive call that cannot be unrolled.
ack(4,2) = 2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880933348101038234342907263181822949382118812668869506364761547029165041871916351587966347219442930927982084309104855990570159318959639524863372367203002916969592156108764948889254090805911457037675208500206671563702366126359747144807111774815880914135742720967190151836282560618091458852699826141425030123391108273603843767876449043205960379124490905707560314035076162562476031863793126484703743782954975613770981604614413308692118102485959152380195331030292162800160568670105651646750568038741529463842244845292537361442533614373729088303794601274724958414864915930647252015155693922628180691650796381064132275307267143998158508811292628901134237782705567421080070065283963322155077831214288551675554073345107213112427399562982719769150054883905223804357045848197956393157853510018992000024141963706813559840464039472194016069517690156119726982337890017641517190051133466306898140219383481435426387306539552969691388024158161859561100640362119796101859534802787167200122604642492385111393400464351623867567078745259464670903886547743483217897012764455529409092021959585751622973333576159552394885297579954028471943529913543763705986928913757153740001986394332464890052543106629669165243419174691389632476560289415199775477703138064781342309596190960654591300890188887588084733625956065444888501447335706058817090162108499714529568344061979690565469813631162053579369791403236328496233046421066136200220175787851857409162050489711781820400187282939943446186224328009837323764931814789848119452713007440220765680910376203999203492023906626264491909167985461515778839060397720759279378852241294301017458086862263369284725851403039615558564330385450688652213114813638408384778263790459607186876728509763471271988890680478243230394718650525660978150729861141430305816927924971409161059417185352275887504477592218301158780701975535722241400019548102005661773589781499532325208589753463547007786690406429016763808161740550405117670093673202804549339027992491867306539931640720492238474815280619166900933805732120816350707634351669869625020969023162859350071874190579161241536897514808261904847946571736601005892476655445840838334790544144817684255327207315586349347605137419779525190365032198020108764738368682531025183377533908861426184800374008082238104076468878471647552945326947661700424461063311238021134588694532200116564076327023074292426051582811070387018345324567635625951430032037432740780879056283663406965030844225855967039271869461158513793386475699748568670079823960604393478850861649260304945061743412365828352144806726676841807083754862211408236579802961200027441324438432402331257403545019352428776430880232850855886089962774458164680857875115807014743763867976955049991643998284357290415378143438847303484261903388841494031366139854257635577105335580206622185577060082551288893332226436281984838613239570676191409638533832374343758830859233722284644287996245605476932428998432652677378373173288063210753211238680604674708428051166488709084770291208161104912555598322366244868556651402684641209694982590565519216188104341226838996283071654868525536914850299539675503954938371853405900096187489473992880432496373165753803673586710175783994818471798498246948060532081996066183434012476096639519778021441199752546704080608499344178256285092726523709898651539462193004607364507926212975917698293892367015170992091531567814439791248475706237804600009918293321306880570046591458387208088016887445835557926258465124763087148566313528934166117490617526671492672176128330845273936469244582892571388877839056300482483799839692029222215486145902373478222682521639957440801727144146179559226175083889020074169926238300282286249284182671243405751424188569994272331606998712986882771820617214453142574944015066139463169197629181506579745526236191224848063890033669074365989226349564114665503062965960199720636202603521917776740668777463549375318899587866282125469797102065747232721372918144666659421872003474508942830911535189271114287108376159222380276605327823351661555149369375778466670145717971901227117812780450240026384758788339396817962950690798817121690686929538248529830023476068454114178139110648560236549754227497231007615131870024053910510913817843721791422528587432098524957878034683703337818421444017138688124249984418618129271198533315382567321870421530631197748535214670955334626336610864667332292409879849256691109516143618601548909740241913509623043612196128165950518666022030715613684732364660868905014263913906515063908199378852318365059897299125404479443425166774299659811849233151555272883274028352688442408752811283289980625912673699546247341543333500147231430612750390307397135252069338173843322950701049061867539433130784798015655130384758155685236218010419650255596181934986315913233036096461905990236112681196023441843363334594927631946101716652913823717182394299216272538461776065694542297877071383198817036964588689811863210976900355735884624464835706291453052757101278872027965364479724025405448132748391794128826423835171949197209797145936887537198729130831738033911016128547415377377715951728084111627597186384924222802373441925469991983672192131287035585307966942713416391033882754318613643490100943197409047331014476299861725424423355612237435715825933382804986243892498222780715951762757847109475119033482241412025182688713728193104253478196128440176479531505057110722974314569915223451643121848657575786528197564843508958384722923534559464521215831657751471298708225909292655638836651120681943836904116252668710044560243704200663709001941185557160472044643696932850060046928140507119069261393993902735534545567470314903886022024639948260501762431969305640666366626090207048887438898907498152865444381862917382901051820869936382661868303915273264581286782806601337500096593364625146091723180312930347877421234679118454791311109897794648216922505629399956793483801699157439700537542134485874586856047286751065423341893839099110586465595113646061055156838541217459801807133163612573079611168343863767667307354583494789788316330129240800836356825939157113130978030516441716682518346573675934198084958947940983292500086389778563494693212473426103062713745077286156922596628573857905533240641849018451328284632709269753830867308409142247659474439973348130810986399417379789657010687026734161967196591599588537834822988270125605842365589539690306474965584147981310997157542043256395776070485100881578291408250777738559790129129407309462785944505859412273194812753225152324801503466519048228961406646890305102510916237770448486230229488966711380555607956620732449373374027836767300203011615227008921843515652121379215748206859356920790214502277133099987729459596952817044582181956080965811702798062669891205061560742325686842271306295009864421853470810407128917646906550836129916694778023822502789667843489199409657361704586786242554006942516693979292624714524945408858422726153755260071904336329196375777502176005195800693847635789586878489536872122898557806826518192703632099480155874455575175312736471421295536494084385586615208012115079075068553344489258693283859653013272046970694571546959353658571788894862333292465202735853188533370948455403336565356988172582528918056635488363743793348411845580168331827676834646291995605513470039147876808640322629616641560667508153710646723108461964247537490553744805318226002710216400980584497526023035640038083472053149941172965736785066421400842696497103241919182121213206939769143923368374709228267738708132236680086924703491586840991153098315412063566123187504305467536983230827966457417620806593177265685841681837966106144963432544111706941700222657817358351259821080769101961052229263879745049019254311900620561906577452416191913187533984049343976823310298465893318373015809592522829206820862230332585280119266496314441316442773003237792274712330696417149945532261035475145631290668854345426869788447742981777493710117614651624183616680254815296335308490849943006763654806102940094693750609845588558043970485914449584445079978497045583550685408745163316464118083123079704389849190506587586425810738422420591191941674182490452700288263983057950057341711487031187142834184499153456702915280104485145176055306971441761368582384102787659324662689978418319620312262421177391477208004883578333569204533935953254564897028558589735505751235129536540502842081022785248776603574246366673148680279486052445782673626230852978265057114624846595914210278122788941448163994973881884622768244851622051817076722169863265701654316919742651230041757329904473537672536845792754365412826553581858046840069367718605020070547247548400805530424951854495267247261347318174742180078574693465447136036975884118029408039616746946288540679172138601225419503819704538417268006398820656328792839582708510919958839448297775647152026132871089526163417707151642899487953564854553553148754978134009964854498635824847690590033116961303766127923464323129706628411307427046202032013368350385425360313636763575212604707425311209233402837482949453104727418969287275572027615272268283376741393425652653283068469997597097750005560889932685025049212884068274139881631540456490350775871680074055685724021758685439053228133770707415830756269628316955687424060527726485853050611356384851965918968649596335568216975437621430778665934730450164822432964891270709898076676625671517269062058815549666382573829274182082278960684488222983394816670984039024283514306813767253460126007269262969468672750794346190439996618979611928750519442356402644303271737341591281496056168353988188569484045342311424613559925272330064881627466723523751234311893442118885085079358163848994487544756331689213869675574302737953785262542329024881047181939037220666894702204258836895840939998453560948869946833852579675161882159410981624918741813364726965123980677561947912557957446471427868624053750576104204267149366084980238274680575982591331006919941904651906531171908926077949119217946407355129633864523035673345588033313197080365457184791550432654899559705862888286866606618021882248602144999973122164138170653480175510438406624412822803616648904257377640956326482825258407669045608439490325290526337532316509087681336614242398309530806549661879381949120033919489494065132398816642080088395554942237096734840072642705701165089075196155370186264797456381187856175457113400473810762763014953309735174180655479112660938034311378532532883533352024934365979129341284854970946826329075830193072665337782559314331110963848053940859283988907796210479847919686876539987477095912788727475874439806779824968278272200926449944559380414608770641941810440758269805688038949654616587983904660587645341810289907194293021774519976104495043196841503455514044820928933378657363052830619990077748726922998608279053171691876578860908941817057993404890218441559791092676862796597583952483926734883634745651687016166240642424241228961118010615682342539392180052483454723779219911228595914191877491793823340010078128326506710281781396029120914720100947878752551263372884222353869490067927664511634758101193875319657242121476038284774774571704578610417385747911301908583877890152334343013005282797038580359815182929600305682612091950943737325454171056383887047528950563961029843641360935641632589408137981511693338619797339821670761004607980096016024823096943043806956620123213650140549586250615282588033022908385812478469315720323233601899469437647726721879376826431828382603564520699468630216048874528424363593558622333506235945002890558581611275341783750455936126130852640828051213873177490200249552738734585956405160830583053770732533971552620444705429573538361113677523169972740292941674204423248113875075631319078272188864053374694213842169928862940479635305150560788126366206497231257579019598873041195626227343728900516561111094111745277965482790471250581999077498063821559376885546498822938985408291325129076478386322494781016753491693489288104203015610283386143827378160946341335383578340765314321417150655877547820252454780657301342277470616744241968952613164274104695474621483756288299771804186785084546965619150908695874251184435837306590951460980451247409411373899927822492983367796011015387096129749705566301637307202750734759922943792393824427421186158236161317886392553095117188421298508307238259729144142251579403883011359083331651858234967221259621812507058113759495525022747274674369887131926670769299199084467161228738858457584622726573330753735572823951616964175198675012681745429323738294143824814377139861906716657572945807804820559511881687188075212971832636442155336787751274766940790117057509819575084563565217389544179875074523854455200133572033332379895074393905312918212255259833790909463630202185353848854825062897715616963860712382771725621313460549401770413581731931763370136332252819127547191443450920711848838366818174263342949611870091503049165339464763717766439120798347494627397822171502090670190302469762151278521956142070806461631373236517853976292092025500288962012970141379640038055734949269073535145961208674796547733692958773628635660143767964038430796864138563447801328261284589184898528048048844180821639423974014362903481665458114454366460032490618763039502356402044530748210241366895196644221339200757479128683805175150634662569391937740283512075666260829890491877287833852178522792045771846965855278790447562192663992008409302075673925363735628390829817577902153202106409617373283598494066652141198183810884515459772895164572131897797907491941013148368544639616904607030107596818933741217575988165127000761262789169510406315857637534787420070222051070891257612361658026806815858499852631465878086616800733264676830206391697203064894405628195406190685242003053463156621891327309069687353181641094514288036605995220248248886711554429104721929134248346438705368508648749099178812670565665387191049721820042371492740164460943459845392536706132210616533085662021188968234005752675486101476993688738209584552211571923479686888160853631615862880150395949418529489227074410828207169303387818084936204018255222271010985653444817207470756019245915599431072949578197878590578940052540122867517142511184356437184053563024181225473266093302710397968091064939272722683035410467632591355279683837705019855234621222858410557119921731717969804339317707750755627056047831779844447637560254637033369247114220815519973691371975163241302748712199863404548248524570118553342675264715978310731245663429805221455494156252724028915333354349341217862037007260315279870771872491234494477147909520734761385425485311552773301030342476835865496093722324007154518129732692081058424090557725645803681462234493189708138897143299831347617799679712453782310703739151473878692119187566700319321281896803322696594459286210607438827416919465162267632540665070881071030394178860564893769816734159025925194611823642945652669372203155504700213598846292758012527715422016629954863130324912311029627923723899766416803497141226527931907636326136814145516376656559839788489381733082668779901962886932296597379951931621187215455287394170243669885593888793316744533363119541518404088283815193421234122820030950313341050704760159987985472529190665222479319715440331794836837373220821885773341623856441380700541913530245943913502554531886454796252260251762928374330465102361057583514550739443339610216229675461415781127197001738611494279501411253280621254775810512972088465263158094806633687670147310733540717710876615935856814098212967730759197382973441445256688770855324570888958320993823432102718224114763732791357568615421252849657903335093152776925505845644010552192644505312073756287744998163646332835816140330175813967359427327690448920361880386754955751806890058532927201493923500525845146706982628548257883267398735220457228239290207144822219885587102896991935873074277815159757620764023951243860202032596596250212578349957710085626386118233813318509014686577064010676278617583772772895892746039403930337271873850536912957126715066896688493880885142943609962012966759079225082275313812849851526902931700263136328942095797577959327635531162066753488651317323872438748063513314512644889967589828812925480076425186586490241111127301357197181381602583178506932244007998656635371544088454866393181708395735780799059730839094881804060935959190907473960904410150516321749681412100765719177483767355751000733616922386537429079457803200042337452807566153042929014495780629634138383551783599764708851349004856973697965238695845994595592090709058956891451141412684505462117945026611750166928260250950770778211950432617383223562437601776799362796099368975191394965033358507155418436456852616674243688920371037495328425927131610537834980740739158633817967658425258036737206469351248652238481341663808061505704829059890696451936440018597120425723007316410009916987524260377362177763430621616744884930810929901009517974541564251204822086714586849255132444266777127863728211331536224301091824391243380214046242223349153559516890816288487989988273630445372432174280215755777967021666317047969728172483392841015642274507271779269399929740308072770395013581545142494049026536105825409373114653104943382484379718606937214444600826798002471229489405761853892203425608302697052876621377373594394224114707074072902725461307358541745691419446487624357682397065703184168467540733466346293673983620004041400714054277632480132742202685393698869787607009590048684650626771363070979821006557285101306601010780633743344773073478653881742681230743766066643312775356466578603715192922768440458273283243808212841218776132042460464900801054731426749260826922155637405486241717031027919996942645620955619816454547662045022411449404749349832206807191352767986747813458203859570413466177937228534940031631599544093684089572533438702986717829770373332806801764639502090023941931499115009105276821119510999063166150311585582835582607179410052528583611369961303442790173811787412061288182062023263849861515656451230047792967563618345768105043341769543067538041113928553792529241347339481050532025708728186307291158911335942014761872664291564036371927602306283840650425441742335464549987055318726887926424102147363698625463747159744354943443899730051742525110877357886390946812096673428152585919924857640488055071329814299359911463239919113959926752576359007446572810191805841807342227734721397723218231771716916400108826112549093361186780575722391018186168549108500885272274374212086524852372456248697662245384819298671129452945515497030585919307198497105414181636968976131126744027009648667545934567059936995464500558921628047976365686133316563907395703272034389175415267500915011198856872708848195531676931681272892143031376818016445477367518353497857924276463354162433601125960252109501612264110346083465648235597934274056868849224458745493776752120324703803035491157544831295275891939893680876327685438769557694881422844311998595700727521393176837831770339130423060958999137314684569010422095161967070506420256733873446115655276175992727151877660010238944760539789516945708802728736225121076224091810066700883474737605156285533943565843756271241244457651663064085939507947550920463932245202535463634444791755661725962187199279186575490857852950012840229035061514937310107009446151011613712423761426722541732055959202782129325725947146417224977321316381845326555279604270541871496236585252458648933254145062642337885651464670604298564781968461593663288954299780722542264790400616019751975007460545150060291806638271497016110987951336633771378434416194053121445291855180136575558667615019373029691932076120009255065081583275508499340768797252369987023567931026804136745718956641431852679054717169962990363015545645090044802789055701968328313630718997699153166679208958768572290600915472919636381673596673959975710326015571920237348580521128117458610065152598883843114511894880552129145775699146577530041384717124577965048175856395072895337539755822087777506072339445587895905719156733
This algorithm takes longer to compute than the Ultimate Answer to Life, the Universe, and Everything took.