[Date Prev][Date Next][Thread Prev][Thread Next]
[Search]
[Date Index]
[Thread Index]
Re: [FWP] Ackerman
On Wed, Jun 27, 2001 at 10:47:37AM +0100, csaba.raduly@sophos.com wrote:
> Do you think your computer has too much memory ? Give it a workout!
>
>
> #!perl -X
> use strict;
> use Math::BigInt;
>
> # $\=$/;
>
> sub Acker
> {
> my ( $m, $n ) = @_;
> if( $m==0 ){
> return $n+1;
> }
> if( $n==0 ){
> return Acker( $m-1, 0 );
> }
> return Acker( $m-1, Acker($m,$n-1) );
> }
>
> my $level = 0;
> my $maxx;
> my $maxy;
>
> sub A
> {
> my ( $x, $y ) = @_;
> $maxx = $x if( $maxx < $x );
> $maxy = $y if( $maxy < $y );
> # $level ++;
> # print ' ' x $level , "Ackerman for $x, $y\n";
> my $rez = ($x>0) ? A($x-1,($y>0)?A($x,$y-1):1) : $y+1;
> # $level --;
> $rez;
> }
>
> sub sigint{
> my ($signal) = @_;
> die "Caught SIG$signal, $maxx,$maxy";
> }
>
> $SIG{INT} = \&sigint;
> $SIG{TERM} = \&sigint;
> $SIG{QUIT} = \&sigint;
> $SIG{KILL} = \&sigint;
>
> for( my $i=0; $i<=4; $i++ )
> {
> for( my $j=0; $j<=7; $j++ )
> {
> $maxx = $maxy = 0;
> print "A( $i, $j ) = ",A( $i, $j ),"\n";
> print "\t\t$maxx,$maxy\n";
> }
> print '-' x 20, "\n";
> }
>
> __END__
>
> This script computes the Ackerman function, The Most Fiendishly Recursive
> Function Known To Man (tm).
Eh, no, it doesn't. It starts off with:
A( 1, 0 ) = 2
1,1
A( 1, 1 ) = 3
1,2
A( 1, 2 ) = 4
1,3
A( 1, 3 ) = 5
1,4
A( 1, 4 ) = 6
1,5
A( 1, 5 ) = 7
1,6
A( 1, 6 ) = 8
1,7
A( 1, 7 ) = 9
1,8
which are numbers that are way too low. The rest of the numbers are
way too low too. Acker (3, 5) for instance is a number with almost
20k digits.
Your program puzzles me. You have a function 'Acker', but you never call
it. You also use Math::BigInt, but you never make objects from that class.
Here's an implementation of the Ackermann function, as defined in [1].
Call the program with two arguments, indicating the max arguments with
call the Ackermann function with, and an optional first "-OPTIMIZE",
which heavily optimizes the calculation of the values.
[1] Edelsbrunner, Herbert: "Algorithms in Combinatorial Geometry", in
Brauer, W., Rozenberg, G., and Salomaa, A. (Eds.) "EATCS Monographs
on Theoretical Computer Science", Berlin: Springer-Verlag, 1987,
pp 377.
#!/opt/perl/bin/perl -ws
use strict;
use Math::BigInt;
my $two = Math::BigInt -> new (2);
my $three = Math::BigInt -> new (3);
my $four = Math::BigInt -> new (4);
use vars qw /$OPTIMIZE/;
sub Ack {
my ($i, $j) = @_;
if ($OPTIMIZE) {
return $four if $j == 2;
return $two * $j if $i == 1;
return $two ** $j if $i == 2;
return $two ** Ack ($three, $j - 1) if $i == 3 && $j >= 2;
}
return $two if $j == 1;
return Ack ($i, $j - 1) + $two if $i == 1;
Ack ($i - 1, Ack ($i, $j - 1))
}
my $i_max = shift || 4;
my $j_max = shift || 3;
foreach my $I (1 .. $i_max) {
my $i = Math::BigInt -> new ($I);
foreach my $J (1 .. $j_max) {
my $j = Math::BigInt -> new ($J);
print "Ack ($i, $j) = ", Ack ($i, $j), "\n";
}
}
__END__
$ ./ack -OPTIMIZE 5 5
Ack (+1, +1) = +2
Ack (+1, +2) = +4
Ack (+1, +3) = +6
Ack (+1, +4) = +8
Ack (+1, +5) = +10
Ack (+2, +1) = +2
Ack (+2, +2) = +4
Ack (+2, +3) = +8
Ack (+2, +4) = +16
Ack (+2, +5) = +32
Ack (+3, +1) = +2
Ack (+3, +2) = +4
Ack (+3, +3) = +16
Ack (+3, +4) = +65536
Ack (+3, +5) = +200352993040684646497907235156025575044782547556975141926501697371089405955631145308950613088093334810103823434290726318182294938211881266886950636476154702916504187191635158796634721944293092798208430910485599057015931895963952486337236720300291696959215610876494888925409080591145703767520850020667156370236612635974714480711177481588091413574272096719015183628256061809145885269982614142503012339110827360384376787644904320596037912449090570756031403507616256247603186379312648470374378295497561377098160461441330869211810248595915238019533103029216280016056867010565164675056803874152946384224484529253736144253361437372908830379460127472495841486491593064725201515569392262818069165079638106413227530726714399815850881129262890113423778270556742108007006528396332215507783121428855167555407334510721311242739956298271976915005488390522380435704584819795639315785351001899200002414196370681355984046403947219401606951769015611972698233789001764151719005113346630689814021!
9383481435426387306539552969691388024158161859561100640362119796101859534802787167200122604642492385111393400464351623867567078745259464670903886547743483217897012764455529409092021959585751622973333576159552394885297579954028471943529913543763705986928913757153740001986394332464890052543106629669165243419174691389632476560289415199775477703138064781342309596190960654591300890188887588084733625956065444888501447335706058817090162108499714529568344061979690565469813631162053579369791403236328496233046421066136200220175787851857409162050489711781820400187282939943446186224328009837323764931814789848119452713007440220765680910376203999203492023906626264491909167985461515778839060397720759279378852241294301017458086862263369284725851403039615558564330385450688652213114813638408384778263790459607186876728509763471271988890680478243230394718650525660978150729861141430305816927924971409161059417185352275887504477592218301158780701975535722241400019548102005661773589781499532325208589!
753463547007786690406429016763808161740550405117670093673!
20280454
9
6900933805732120816350707634351669869625020969023162859350071874190579161241536897514808261904847946571736601005892476655445840838334790544144817684255327207315586349347605137419779525190365032198020108764738368682531025183377533908861426184800374008082238104076468878471647552945326947661700424461063311238021134588694532200116564076327023074292426051582811070387018345324567635625951430032037432740780879056283663406965030844225855967039271869461158513793386475699748568670079823960604393478850861649260304945061743412365828352144806726676841807083754862211408236579802961200027441324438432402331257403545019352428776430880232850855886089962774458164680857875115807014743763867976955049991643998284357290415378143438847303484261903388841494031366139854257635577105335580206622185577060082551288893332226436281984838613239570676191409638533832374343758830859233722284644287996245605476932428998432652677378373173288063210753211238680604674708428051166488709084770291208161104912555598322366!
2448685566514026846412096949825905655192161881043412268389962830716548685255369148502995396755039549383718534059000961874894739928804324963731657538036735867101757839948184717984982469480605320819960661834340124760966395197780214411997525467040806084993441782562850927265237098986515394621930046073645079262129759176982938923670151709920915315678144397912484757062378046000099182933213068805700465914583872080880168874458355579262584651247630871485663135289341661174906175266714926721761283308452739364692445828925713888778390563004824837998396920292222154861459023734782226825216399574408017271441461795592261750838890200741699262383002822862492841826712434057514241885699942723316069987129868827718206172144531425749440150661394631691976291815065797455262361912248480638900336690743659892263495641146655030629659601997206362026035219177767406687774635493753188995878662821254697971020657472327213729181446666594218720034745089428309115351892711142871083761592223802766053278233516615551493!
693757784666701457179719012271178127804502400263847587883!
39396817
9
4178139110648560236549754227497231007615131870024053910510913817843721791422528587432098524957878034683703337818421444017138688124249984418618129271198533315382567321870421530631197748535214670955334626336610864667332292409879849256691109516143618601548909740241913509623043612196128165950518666022030715613684732364660868905014263913906515063908199378852318365059897299125404479443425166774299659811849233151555272883274028352688442408752811283289980625912673699546247341543333500147231430612750390307397135252069338173843322950701049061867539433130784798015655130384758155685236218010419650255596181934986315913233036096461905990236112681196023441843363334594927631946101716652913823717182394299216272538461776065694542297877071383198817036964588689811863210976900355735884624464835706291453052757101278872027965364479724025405448132748391794128826423835171949197209797145936887537198729130831738033911016128547415377377715951728084111627597186384924222802373441925469991983672192131287035!
5853079669427134163910338827543186136434901009431974090473310144762998617254244233556122374357158259333828049862438924982227807159517627578471094751190334822414120251826887137281931042534781961284401764795315050571107229743145699152234516431218486575757865281975648435089583847229235345594645212158316577514712987082259092926556388366511206819438369041162526687100445602437042006637090019411855571604720446436969328500600469281405071190692613939939027355345455674703149038860220246399482605017624319693056406663666260902070488874388989074981528654443818629173829010518208699363826618683039152732645812867828066013375000965933646251460917231803129303478774212346791184547913111098977946482169225056293999567934838016991574397005375421344858745868560472867510654233418938390991105864655951136460610551568385412174598018071331636125730796111683438637676673073545834947897883163301292408008363568259391571131309780305164417166825183465736759341980849589479409832925000863897785634946932124734261!
030627137450772861569225966285738579055332406418490184513!
28284632
7
9417379789657010687026734161967196591599588537834822988270125605842365589539690306474965584147981310997157542043256395776070485100881578291408250777738559790129129407309462785944505859412273194812753225152324801503466519048228961406646890305102510916237770448486230229488966711380555607956620732449373374027836767300203011615227008921843515652121379215748206859356920790214502277133099987729459596952817044582181956080965811702798062669891205061560742325686842271306295009864421853470810407128917646906550836129916694778023822502789667843489199409657361704586786242554006942516693979292624714524945408858422726153755260071904336329196375777502176005195800693847635789586878489536872122898557806826518192703632099480155874455575175312736471421295536494084385586615208012115079075068553344489258693283859653013272046970694571546959353658571788894862333292465202735853188533370948455403336565356988172582528918056635488363743793348411845580168331827676834646291995605513470039147876808640322629!
6166415606675081537106467231084619642475374905537448053182260027102164009805844975260230356400380834720531499411729657367850664214008426964971032419191821212132069397691439233683747092282677387081322366800869247034915868409911530983154120635661231875043054675369832308279664574176208065931772656858416818379661061449634325441117069417002226578173583512598210807691019610522292638797450490192543119006205619065774524161919131875339840493439768233102984658933183730158095925228292068208622303325852801192664963144413164427730032377922747123306964171499455322610354751456312906688543454268697884477429817774937101176146516241836166802548152963353084908499430067636548061029400946937506098455885580439704859144495844450799784970455835506854087451633164641180831230797043898491905065875864258107384224205911919416741824904527002882639830579500573417114870311871428341844991534567029152801044851451760553069714417613685823841027876593246626899784183196203122624211773914772080048835783335692045339!
359532545648970285585897355057512351295365405028420810227!
85248776
6
5057114624846595914210278122788941448163994973881884622768244851622051817076722169863265701654316919742651230041757329904473537672536845792754365412826553581858046840069367718605020070547247548400805530424951854495267247261347318174742180078574693465447136036975884118029408039616746946288540679172138601225419503819704538417268006398820656328792839582708510919958839448297775647152026132871089526163417707151642899487953564854553553148754978134009964854498635824847690590033116961303766127923464323129706628411307427046202032013368350385425360313636763575212604707425311209233402837482949453104727418969287275572027615272268283376741393425652653283068469997597097750005560889932685025049212884068274139881631540456490350775871680074055685724021758685439053228133770707415830756269628316955687424060527726485853050611356384851965918968649596335568216975437621430778665934730450164822432964891270709898076676625671517269062058815549666382573829274182082278960684488222983394816670984039024283!
5143068137672534601260072692629694686727507943461904399966189796119287505194423564026443032717373415912814960561683539881885694840453423114246135599252723300648816274667235237512343118934421188850850793581638489944875447563316892138696755743027379537852625423290248810471819390372206668947022042588368958409399984535609488699468338525796751618821594109816249187418133647269651239806775619479125579574464714278686240537505761042042671493660849802382746805759825913310069199419046519065311719089260779491192179464073551296338645230356733455880333131970803654571847915504326548995597058628882868666066180218822486021449999731221641381706534801755104384066244128228036166489042573776409563264828252584076690456084394903252905263375323165090876813366142423983095308065496618793819491200339194894940651323988166420800883955549422370967348400726427057011650890751961553701862647974563811878561754571134004738107627630149533097351741806554791126609380343113785325328835333520249343659791293412848549!
709468263290758301930726653377825593143311109638480539408!
59283988
9
9806779824968278272200926449944559380414608770641941810440758269805688038949654616587983904660587645341810289907194293021774519976104495043196841503455514044820928933378657363052830619990077748726922998608279053171691876578860908941817057993404890218441559791092676862796597583952483926734883634745651687016166240642424241228961118010615682342539392180052483454723779219911228595914191877491793823340010078128326506710281781396029120914720100947878752551263372884222353869490067927664511634758101193875319657242121476038284774774571704578610417385747911301908583877890152334343013005282797038580359815182929600305682612091950943737325454171056383887047528950563961029843641360935641632589408137981511693338619797339821670761004607980096016024823096943043806956620123213650140549586250615282588033022908385812478469315720323233601899469437647726721879376826431828382603564520699468630216048874528424363593558622333506235945002890558581611275341783750455936126130852640828051213873177490200249!
5527387345859564051608305830537707325339715526204447054295735383611136775231699727402929416742044232481138750756313190782721888640533746942138421699288629404796353051505607881263662064972312575790195988730411956262273437289005165611110941117452779654827904712505819990774980638215593768855464988229389854082913251290764783863224947810167534916934892881042030156102833861438273781609463413353835783407653143214171506558775478202524547806573013422774706167442419689526131642741046954746214837562882997718041867850845469656191509086958742511844358373065909514609804512474094113738999278224929833677960110153870961297497055663016373072027507347599229437923938244274211861582361613178863925530951171884212985083072382597291441422515794038830113590833316518582349672212596218125070581137594955250227472746743698871319266707692991990844671612287388584575846227265733307537355728239516169641751986750126817454293237382941438248143771398619067166575729458078048205595118816871880752129718326364421553!
367877512747669407901170575098195750845635652173895441798!
75074523
8
3790909463630202185353848854825062897715616963860712382771725621313460549401770413581731931763370136332252819127547191443450920711848838366818174263342949611870091503049165339464763717766439120798347494627397822171502090670190302469762151278521956142070806461631373236517853976292092025500288962012970141379640038055734949269073535145961208674796547733692958773628635660143767964038430796864138563447801328261284589184898528048048844180821639423974014362903481665458114454366460032490618763039502356402044530748210241366895196644221339200757479128683805175150634662569391937740283512075666260829890491877287833852178522792045771846965855278790447562192663992008409302075673925363735628390829817577902153202106409617373283598494066652141198183810884515459772895164572131897797907491941013148368544639616904607030107596818933741217575988165127000761262789169510406315857637534787420070222051070891257612361658026806815858499852631465878086616800733264676830206391697203064894405628195406190685!
2420030534631566218913273090696873531816410945142880366059952202482488867115544291047219291342483464387053685086487490991788126705656653871910497218200423714927401644609434598453925367061322106165330856620211889682340057526754861014769936887382095845522115719234796868881608536316158628801503959494185294892270744108282071693033878180849362040182552222710109856534448172074707560192459155994310729495781978785905789400525401228675171425111843564371840535630241812254732660933027103979680910649392727226830354104676325913552796838377050198552346212228584105571199217317179698043393177077507556270560478317798444476375602546370333692471142208155199736913719751632413027487121998634045482485245701185533426752647159783107312456634298052214554941562527240289153333543493412178620370072603152798707718724912344944771479095207347613854254853115527733010303424768358654960937223240071545181297326920810584240905577256458036814622344931897081388971432998313476177996797124537823107037391514738786921!
191875667003193212818968033226965944592862106074388274169!
19465162
2
5925194611823642945652669372203155504700213598846292758012527715422016629954863130324912311029627923723899766416803497141226527931907636326136814145516376656559839788489381733082668779901962886932296597379951931621187215455287394170243669885593888793316744533363119541518404088283815193421234122820030950313341050704760159987985472529190665222479319715440331794836837373220821885773341623856441380700541913530245943913502554531886454796252260251762928374330465102361057583514550739443339610216229675461415781127197001738611494279501411253280621254775810512972088465263158094806633687670147310733540717710876615935856814098212967730759197382973441445256688770855324570888958320993823432102718224114763732791357568615421252849657903335093152776925505845644010552192644505312073756287744998163646332835816140330175813967359427327690448920361880386754955751806890058532927201493923500525845146706982628548257883267398735220457228239290207144822219885587102896991935873074277815159757620764023951!
2438602020325965962502125783499577100856263861182338133185090146865770640106762786175837727728958927460394039303372718738505369129571267150668966884938808851429436099620129667590792250822753138128498515269029317002631363289420957975779593276355311620667534886513173238724387480635133145126448899675898288129254800764251865864902411111273013571971813816025831785069322440079986566353715440884548663931817083957357807990597308390948818040609359591909074739609044101505163217496814121007657191774837673557510007336169223865374290794578032000423374528075661530429290144957806296341383835517835997647088513490048569736979652386958459945955920907090589568914511414126845054621179450266117501669282602509507707782119504326173832235624376017767993627960993689751913949650333585071554184364568526166742436889203710374953284259271316105378349807407391586338179676584252580367372064693512486522384813416638080615057048290598906964519364400185971204257230073164100099169875242603773621777634306216167448!
849308109299010095179745415642512048220867145868492551324!
44266777
1
9153559516890816288487989988273630445372432174280215755777967021666317047969728172483392841015642274507271779269399929740308072770395013581545142494049026536105825409373114653104943382484379718606937214444600826798002471229489405761853892203425608302697052876621377373594394224114707074072902725461307358541745691419446487624357682397065703184168467540733466346293673983620004041400714054277632480132742202685393698869787607009590048684650626771363070979821006557285101306601010780633743344773073478653881742681230743766066643312775356466578603715192922768440458273283243808212841218776132042460464900801054731426749260826922155637405486241717031027919996942645620955619816454547662045022411449404749349832206807191352767986747813458203859570413466177937228534940031631599544093684089572533438702986717829770373332806801764639502090023941931499115009105276821119510999063166150311585582835582607179410052528583611369961303442790173811787412061288182062023263849861515656451230047792967563618!
3457681050433417695430675380411139285537925292413473394810505320257087281863072911589113359420147618726642915640363719276023062838406504254417423354645499870553187268879264241021473636986254637471597443549434438997300517425251108773578863909468120966734281525859199248576404880550713298142993599114632399191139599267525763590074465728101918058418073422277347213977232182317717169164001088261125490933611867805757223910181861685491085008852722743742120865248523724562486976622453848192986711294529455154970305859193071984971054141816369689761311267440270096486675459345670599369954645005589216280479763656861333165639073957032720343891754152675009150111988568727088481955316769316812728921430313768180164454773675183534978579242764633541624336011259602521095016122641103460834656482355979342740568688492244587454937767521203247038030354911575448312952758919398936808763276854387695576948814228443119985957007275213931768378317703391304230609589991373146845690104220951619670705064202567338734!
461156552761759927271518776600102389447605397895169457088!
02728736
2
3756271241244457651663064085939507947550920463932245202535463634444791755661725962187199279186575490857852950012840229035061514937310107009446151011613712423761426722541732055959202782129325725947146417224977321316381845326555279604270541871496236585252458648933254145062642337885651464670604298564781968461593663288954299780722542264790400616019751975007460545150060291806638271497016110987951336633771378434416194053121445291855180136575558667615019373029691932076120009255065081583275508499340768797252369987023567931026804136745718956641431852679054717169962990363015545645090044802789055701968328313630718997699153166679208958768572290600915472919636381673596673959975710326015571920237348580521128117458610065152598883843114511894880552129145775699146577530041384717124577965048175856395072895337539755822087777506072339445587895905719156736
Ack (+4, +1) = +2
Ack (+4, +2) = +4
Ack (+4, +3) = +65536
Deep recursion on subroutine "main::Ack" at ./myack line 19.
<Killed after several minutes>
Abigail
==== Want to unsubscribe from Fun With Perl? Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
==== unsubscribe