stack overflow for ackerman
Pieter
I have started programming lisp... yesterday :)
I got ackerman to work and this is my implimentation.
(defun ackerman (x y)
(cond
((< x 0) "Error: X too small")
((< y 0) "Error: Y too small")
((= x 0) (+ y 1))
((= y 0) (ackerman (- x 1) 1))
(t (ackerman (- x 1) (ackerman x (- y 1))))
)
)
it works (As far as I can test it) but for (ackerman 4 4) give the
following:
---<lisp output>---
[7]> (ackerman 4 4)
*** - Program stack overflow. RESET
---</lisp output>---
I am using clisp on Windows 2000. I start clisp with "-m 80MB". Is
there another way I can set up the stack to be bigger?
Regards
Pieter
Joe Marshall
Pieter
> Have you estimated the depth of stack needed?
I am not completely sure that I understand what you are asking. :( I
know that (ackerman 4 4)'s answer is HUGE and that the stack must be
VERY big. I know this because of other implimentations though.
Pieter
Joe Marshall
I'm just asking if you have an idea of exactly how big ``VERY big''
is. I think you have underestimated it.
Christopher Jeris
> I'm just asking if you have an idea of exactly how big ``VERY big''
> is. I think you have underestimated it.
in case the OP doesn't know about this resource: you can find A(4,4)
at the Online Encyclopedia of Integer Sequences:
http://www.research.att.com/~njas/sequences/
see sequence number A046859.
--
Chris Jeris cje...@oinvzer.net Apply (1 6 2 4)(3 7) to domain to reply.
Kaz Kylheku
> it works (As far as I can test it) but for (ackerman 4 4) give the
> following:
> ---<lisp output>---
> [7]> (ackerman 4 4)
> *** - Program stack overflow. RESET
> ---</lisp output>---
Do you have any idea how big this number is, by the way? What exactly
do you expect to happen?
> I am using clisp on Windows 2000. I start clisp with "-m 80MB". Is
> there another way I can set up the stack to be bigger?
Do you really think that the stack depth is all that stands in your
way? The value you are trying to compute involves numbers like
65536
2
2
have you tried evaluating (expt 2 (expt 2 65536))? On the same Lisp
implementation that you are using, I get:
*** overflow during multiplication of large numbers
Skill testing question: in the straightforward binary representation,
how many bits of storage would the number (expt 2 (expt 2 65536))
require?
Also, there are two N's in Ackermann, by the way.
Kaz Kylheku
What makes you think that bignum integers are stored on the stack?
They are usually represented as references to heap-allocated bit
strings. The stack frame contains just these references, not the bit
strings themselves. The references are tiny scalar quantities that
typically fit in a machine register: 32 bits or maybe 64 these days.
Karsten Poeck
"Pieter" <pie...@lynxgeo.com> wrote in message
news:8fb8b19a.04011...@posting.google.com...
I think ackermann 4 2 is the largest computation that can be done.
Take a look at the following code (from Sam Steingold) and calculate for
yourself what a number ackerman 4 4 would be
(defun ackermann1 (aa bb)
(declare (optimize (speed 3) (safety 0)))
(cond ((zerop aa)
(1+ bb))
((= 1 aa) (+ 2 bb))
((= 2 aa) (+ 3 (* 2 bb)))
((= 3 aa) (- (ash 1 (+ 3 bb)) 3))
(t (if (zerop bb)
(ackermann1 (1- aa) 1)
(ackermann1 (1- aa) (ackermann1 aa (1- bb)))))))
Karsten
[9]> (ackermann1 4 2)
2003529930406846464979072351560255750447825475569751419265016973710894059556
3114
5308950613088093334810103823434290726318182294938211881266886950636476154702
9165
0418719163515879663472194429309279820843091048559905701593189596395248633723
6720
3002916969592156108764948889254090805911457037675208500206671563702366126359
7471
4480711177481588091413574272096719015183628256061809145885269982614142503012
3391
1082736038437678764490432059603791244909057075603140350761625624760318637931
2648
4703743782954975613770981604614413308692118102485959152380195331030292162800
1605
6867010565164675056803874152946384224484529253736144253361437372908830379460
1274
7249584148649159306472520151556939226281806916507963810641322753072671439981
5850
8811292628901134237782705567421080070065283963322155077831214288551675554073
3451
0721311242739956298271976915005488390522380435704584819795639315785351001899
2000
0241419637068135598404640394721940160695176901561197269823378900176415171900
5113
3466306898140219383481435426387306539552969691388024158161859561100640362119
7961
0185953480278716720012260464249238511139340046435162386756707874525946467090
3886
5477434832178970127644555294090920219595857516229733335761595523948852975799
5402
8471943529913543763705986928913757153740001986394332464890052543106629669165
2434
1917469138963247656028941519977547770313806478134230959619096065459130089018
8887
5880847336259560654448885014473357060588170901621084997145295683440619796905
6546
9813631162053579369791403236328496233046421066136200220175787851857409162050
4897
1178182040018728293994344618622432800983732376493181478984811945271300744022
0765
6809103762039992034920239066262644919091679854615157788390603977207592793788
5224
1294301017458086862263369284725851403039615558564330385450688652213114813638
4083
8477826379045960718687672850976347127198889068047824323039471865052566097815
0729
8611414303058169279249714091610594171853522758875044775922183011587807019755
3572
2241400019548102005661773589781499532325208589753463547007786690406429016763
8081
6174055040511767009367320280454933902799249186730653993164072049223847481528
0619
1669009338057321208163507076343516698696250209690231628593500718741905791612
4153
6897514808261904847946571736601005892476655445840838334790544144817684255327
2073
1558634934760513741977952519036503219802010876473836868253102518337753390886
1426
1848003740080822381040764688784716475529453269476617004244610633112380211345
8869
4532200116564076327023074292426051582811070387018345324567635625951430032037
4327
4078087905628366340696503084422585596703927186946115851379338647569974856867
0079
8239606043934788508616492603049450617434123658283521448067266768418070837548
6221
1408236579802961200027441324438432402331257403545019352428776430880232850855
8860
8996277445816468085787511580701474376386797695504999164399828435729041537814
3438
8473034842619033888414940313661398542576355771053355802066221855770600825512
8889
3332226436281984838613239570676191409638533832374343758830859233722284644287
9962
4560547693242899843265267737837317328806321075321123868060467470842805116648
8709
0847702912081611049125555983223662448685566514026846412096949825905655192161
8810
4341226838996283071654868525536914850299539675503954938371853405900096187489
4739
9288043249637316575380367358671017578399481847179849824694806053208199606618
3434
0124760966395197780214411997525467040806084993441782562850927265237098986515
3946
2193004607364507926212975917698293892367015170992091531567814439791248475706
2378
0460000991829332130688057004659145838720808801688744583555792625846512476308
7148
5663135289341661174906175266714926721761283308452739364692445828925713888778
3905
6300482483799839692029222215486145902373478222682521639957440801727144146179
5592
2617508388902007416992623830028228624928418267124340575142418856999427233160
6998
7129868827718206172144531425749440150661394631691976291815065797455262361912
2484
8063890033669074365989226349564114665503062965960199720636202603521917776740
6687
7746354937531889958786628212546979710206574723272137291814466665942187200347
4508
9428309115351892711142871083761592223802766053278233516615551493693757784666
7014
5717971901227117812780450240026384758788339396817962950690798817121690686929
5382
4852983002347606845411417813911064856023654975422749723100761513187002405391
0510
9138178437217914225285874320985249578780346837033378184214440171386881242499
8441
8618129271198533315382567321870421530631197748535214670955334626336610864667
3322
9240987984925669110951614361860154890974024191350962304361219612816595051866
6022
0307156136847323646608689050142639139065150639081993788523183650598972991254
0447
9443425166774299659811849233151555272883274028352688442408752811283289980625
9126
7369954624734154333350014723143061275039030739713525206933817384332295070104
9061
8675394331307847980156551303847581556852362180104196502555961819349863159132
3303
6096461905990236112681196023441843363334594927631946101716652913823717182394
2992
1627253846177606569454229787707138319881703696458868981186321097690035573588
4624
4648357062914530527571012788720279653644797240254054481327483917941288264238
3517
1949197209797145936887537198729130831738033911016128547415377377715951728084
1116
2759718638492422280237344192546999198367219213128703558530796694271341639103
3882
7543186136434901009431974090473310144762998617254244233556122374357158259333
8280
4986243892498222780715951762757847109475119033482241412025182688713728193104
2534
7819612844017647953150505711072297431456991522345164312184865757578652819756
4843
5089583847229235345594645212158316577514712987082259092926556388366511206819
4383
6904116252668710044560243704200663709001941185557160472044643696932850060046
9281
4050711906926139399390273553454556747031490388602202463994826050176243196930
5640
6663666260902070488874388989074981528654443818629173829010518208699363826618
6830
3915273264581286782806601337500096593364625146091723180312930347877421234679
1184
5479131110989779464821692250562939995679348380169915743970053754213448587458
6856
0472867510654233418938390991105864655951136460610551568385412174598018071331
6361
2573079611168343863767667307354583494789788316330129240800836356825939157113
1309
7803051644171668251834657367593419808495894794098329250008638977856349469321
2473
4261030627137450772861569225966285738579055332406418490184513282846327092697
5383
0867308409142247659474439973348130810986399417379789657010687026734161967196
5915
9958853783482298827012560584236558953969030647496558414798131099715754204325
6395
7760704851008815782914082507777385597901291294073094627859445058594122731948
1275
3225152324801503466519048228961406646890305102510916237770448486230229488966
7113
8055560795662073244937337402783676730020301161522700892184351565212137921574
8206
8593569207902145022771330999877294595969528170445821819560809658117027980626
6989
1205061560742325686842271306295009864421853470810407128917646906550836129916
6947
7802382250278966784348919940965736170458678624255400694251669397929262471452
4945
4088584227261537552600719043363291963757775021760051958006938476357895868784
8953
6872122898557806826518192703632099480155874455575175312736471421295536494084
3855
8661520801211507907506855334448925869328385965301327204697069457154695935365
8571
7888948623332924652027358531885333709484554033365653569881725825289180566354
8836
3743793348411845580168331827676834646291995605513470039147876808640322629616
6415
6066750815371064672310846196424753749055374480531822600271021640098058449752
6023
0356400380834720531499411729657367850664214008426964971032419191821212132069
3976
9143923368374709228267738708132236680086924703491586840991153098315412063566
1231
8750430546753698323082796645741762080659317726568584168183796610614496343254
4111
7069417002226578173583512598210807691019610522292638797450490192543119006205
6190
6577452416191913187533984049343976823310298465893318373015809592522829206820
8622
3033258528011926649631444131644277300323779227471233069641714994553226103547
5145
6312906688543454268697884477429817774937101176146516241836166802548152963353
0849
0849943006763654806102940094693750609845588558043970485914449584445079978497
0455
8355068540874516331646411808312307970438984919050658758642581073842242059119
1941
6741824904527002882639830579500573417114870311871428341844991534567029152801
0448
5145176055306971441761368582384102787659324662689978418319620312262421177391
4772
0800488357833356920453393595325456489702855858973550575123512953654050284208
1022
7852487766035742463666731486802794860524457826736262308529782650571146248465
9591
4210278122788941448163994973881884622768244851622051817076722169863265701654
3169
1974265123004175732990447353767253684579275436541282655358185804684006936771
8605
0200705472475484008055304249518544952672472613473181747421800785746934654471
3603
6975884118029408039616746946288540679172138601225419503819704538417268006398
8206
5632879283958270851091995883944829777564715202613287108952616341770715164289
9487
9535648545535531487549781340099648544986358248476905900331169613037661279234
6432
3129706628411307427046202032013368350385425360313636763575212604707425311209
2334
0283748294945310472741896928727557202761527226828337674139342565265328306846
9997
5970977500055608899326850250492128840682741398816315404564903507758716800740
5568
5724021758685439053228133770707415830756269628316955687424060527726485853050
6113
5638485196591896864959633556821697543762143077866593473045016482243296489127
0709
8980766766256715172690620588155496663825738292741820822789606844882229833948
1667
0984039024283514306813767253460126007269262969468672750794346190439996618979
6119
2875051944235640264430327173734159128149605616835398818856948404534231142461
3559
9252723300648816274667235237512343118934421188850850793581638489944875447563
3168
9213869675574302737953785262542329024881047181939037220666894702204258836895
8409
3999845356094886994683385257967516188215941098162491874181336472696512398067
7561
9479125579574464714278686240537505761042042671493660849802382746805759825913
3100
6919941904651906531171908926077949119217946407355129633864523035673345588033
3131
9708036545718479155043265489955970586288828686660661802188224860214499997312
2164
1381706534801755104384066244128228036166489042573776409563264828252584076690
4560
8439490325290526337532316509087681336614242398309530806549661879381949120033
9194
8949406513239881664208008839555494223709673484007264270570116508907519615537
0186
2647974563811878561754571134004738107627630149533097351741806554791126609380
3431
1378532532883533352024934365979129341284854970946826329075830193072665337782
5593
1433111096384805394085928398890779621047984791968687653998747709591278872747
5874
4398067798249682782722009264499445593804146087706419418104407582698056880389
4965
4616587983904660587645341810289907194293021774519976104495043196841503455514
0448
2092893337865736305283061999007774872692299860827905317169187657886090894181
7057
9934048902184415597910926768627965975839524839267348836347456516870161662406
4242
4241228961118010615682342539392180052483454723779219911228595914191877491793
8233
4001007812832650671028178139602912091472010094787875255126337288422235386949
0067
9276645116347581011938753196572421214760382847747745717045786104173857479113
0190
8583877890152334343013005282797038580359815182929600305682612091950943737325
4541
7105638388704752895056396102984364136093564163258940813798151169333861979733
9821
6707610046079800960160248230969430438069566201232136501405495862506152825880
3302
2908385812478469315720323233601899469437647726721879376826431828382603564520
6994
6863021604887452842436359355862233350623594500289055858161127534178375045593
6126
1308526408280512138731774902002495527387345859564051608305830537707325339715
5262
0444705429573538361113677523169972740292941674204423248113875075631319078272
1888
6405337469421384216992886294047963530515056078812636620649723125757901959887
3041
1956262273437289005165611110941117452779654827904712505819990774980638215593
7688
5546498822938985408291325129076478386322494781016753491693489288104203015610
2833
8614382737816094634133538357834076531432141715065587754782025245478065730134
2277
4706167442419689526131642741046954746214837562882997718041867850845469656191
5090
8695874251184435837306590951460980451247409411373899927822492983367796011015
3870
9612974970556630163730720275073475992294379239382442742118615823616131788639
2553
0951171884212985083072382597291441422515794038830113590833316518582349672212
5962
1812507058113759495525022747274674369887131926670769299199084467161228738858
4575
8462272657333075373557282395161696417519867501268174542932373829414382481437
7139
8619067166575729458078048205595118816871880752129718326364421553367877512747
6694
0790117057509819575084563565217389544179875074523854455200133572033332379895
0743
9390531291821225525983379090946363020218535384885482506289771561696386071238
2771
7256213134605494017704135817319317633701363322528191275471914434509207118488
3836
6818174263342949611870091503049165339464763717766439120798347494627397822171
5020
9067019030246976215127852195614207080646163137323651785397629209202550028896
2012
9701413796400380557349492690735351459612086747965477336929587736286356601437
6796
4038430796864138563447801328261284589184898528048048844180821639423974014362
9034
8166545811445436646003249061876303950235640204453074821024136689519664422133
9200
7574791286838051751506346625693919377402835120756662608298904918772878338521
7852
2792045771846965855278790447562192663992008409302075673925363735628390829817
5779
0215320210640961737328359849406665214119818381088451545977289516457213189779
7907
4919410131483685446396169046070301075968189337412175759881651270007612627891
6951
0406315857637534787420070222051070891257612361658026806815858499852631465878
0866
1680073326467683020639169720306489440562819540619068524200305346315662189132
7309
0696873531816410945142880366059952202482488867115544291047219291342483464387
0536
8508648749099178812670565665387191049721820042371492740164460943459845392536
7061
3221061653308566202118896823400575267548610147699368873820958455221157192347
9686
8881608536316158628801503959494185294892270744108282071693033878180849362040
1825
5222271010985653444817207470756019245915599431072949578197878590578940052540
1228
6751714251118435643718405356302418122547326609330271039796809106493927272268
3035
4104676325913552796838377050198552346212228584105571199217317179698043393177
0775
0755627056047831779844447637560254637033369247114220815519973691371975163241
3027
4871219986340454824852457011855334267526471597831073124566342980522145549415
6252
7240289153333543493412178620370072603152798707718724912344944771479095207347
6138
5425485311552773301030342476835865496093722324007154518129732692081058424090
5577
2564580368146223449318970813889714329983134761779967971245378231070373915147
3878
6921191875667003193212818968033226965944592862106074388274169194651622676325
4066
5070881071030394178860564893769816734159025925194611823642945652669372203155
5047
0021359884629275801252771542201662995486313032491231102962792372389976641680
3497
1412265279319076363261368141455163766565598397884893817330826687799019628869
3229
6597379951931621187215455287394170243669885593888793316744533363119541518404
0882
8381519342123412282003095031334105070476015998798547252919066522247931971544
0331
7948368373732208218857733416238564413807005419135302459439135025545318864547
9625
2260251762928374330465102361057583514550739443339610216229675461415781127197
0017
3861149427950141125328062125477581051297208846526315809480663368767014731073
3540
7177108766159358568140982129677307591973829734414452566887708553245708889583
2099
3823432102718224114763732791357568615421252849657903335093152776925505845644
0105
5219264450531207375628774499816364633283581614033017581396735942732769044892
0361
8803867549557518068900585329272014939235005258451467069826285482578832673987
3522
0457228239290207144822219885587102896991935873074277815159757620764023951243
8602
0203259659625021257834995771008562638611823381331850901468657706401067627861
7583
7727728958927460394039303372718738505369129571267150668966884938808851429436
0996
2012966759079225082275313812849851526902931700263136328942095797577959327635
5311
6206675348865131732387243874806351331451264488996758982881292548007642518658
6490
2411111273013571971813816025831785069322440079986566353715440884548663931817
0839
5735780799059730839094881804060935959190907473960904410150516321749681412100
7657
1917748376735575100073361692238653742907945780320004233745280756615304292901
4495
7806296341383835517835997647088513490048569736979652386958459945955920907090
5895
6891451141412684505462117945026611750166928260250950770778211950432617383223
5624
3760177679936279609936897519139496503335850715541843645685261667424368892037
1037
4953284259271316105378349807407391586338179676584252580367372064693512486522
3848
1341663808061505704829059890696451936440018597120425723007316410009916987524
2603
7736217776343062161674488493081092990100951797454156425120482208671458684925
5132
4442667771278637282113315362243010918243912433802140462422233491535595168908
1628
8487989988273630445372432174280215755777967021666317047969728172483392841015
6422
7450727177926939992974030807277039501358154514249404902653610582540937311465
3104
9433824843797186069372144446008267980024712294894057618538922034256083026970
5287
6621377373594394224114707074072902725461307358541745691419446487624357682397
0657
0318416846754073346634629367398362000404140071405427763248013274220268539369
8869
7876070095900486846506267713630709798210065572851013066010107806337433447730
7347
8653881742681230743766066643312775356466578603715192922768440458273283243808
2128
4121877613204246046490080105473142674926082692215563740548624171703102791999
6942
6456209556198164545476620450224114494047493498322068071913527679867478134582
0385
9570413466177937228534940031631599544093684089572533438702986717829770373332
8068
0176463950209002394193149911500910527682111951099906316615031158558283558260
7179
4100525285836113699613034427901738117874120612881820620232638498615156564512
3004
7792967563618345768105043341769543067538041113928553792529241347339481050532
0257
0872818630729115891133594201476187266429156403637192760230628384065042544174
2335
4645499870553187268879264241021473636986254637471597443549434438997300517425
2511
0877357886390946812096673428152585919924857640488055071329814299359911463239
9191
1395992675257635900744657281019180584180734222773472139772321823177171691640
0108
8261125490933611867805757223910181861685491085008852722743742120865248523724
5624
8697662245384819298671129452945515497030585919307198497105414181636968976131
1267
4402700964866754593456705993699546450055892162804797636568613331656390739570
3272
0343891754152675009150111988568727088481955316769316812728921430313768180164
4547
7367518353497857924276463354162433601125960252109501612264110346083465648235
5979
3427405686884922445874549377675212032470380303549115754483129527589193989368
0876
3276854387695576948814228443119985957007275213931768378317703391304230609589
9913
7314684569010422095161967070506420256733873446115655276175992727151877660010
2389
4476053978951694570880272873622512107622409181006670088347473760515628553394
3565
8437562712412444576516630640859395079475509204639322452025354636344447917556
6172
5962187199279186575490857852950012840229035061514937310107009446151011613712
4237
6142672254173205595920278212932572594714641722497732131638184532655527960427
0541
8714962365852524586489332541450626423378856514646706042985647819684615936632
8895
4299780722542264790400616019751975007460545150060291806638271497016110987951
3366
3377137843441619405312144529185518013657555866761501937302969193207612000925
5065
0815832755084993407687972523699870235679310268041367457189566414318526790547
1716
9962990363015545645090044802789055701968328313630718997699153166679208958768
5722
9060091547291963638167359667395997571032601557192023734858052112811745861006
5152
5988838431145118948805521291457756991465775300413847171245779650481758563950
7289
5337539755822087777506072339445587895905719156733
Erann Gat
For more than you ever wanted to know about large numbers see the chain of
pages beginning with:
http://home.earthlink.net/~mrob/pub/math/largenum.html
and in particular:
http://home.earthlink.net/~mrob/pub/math/largenum-3.html
Page 2 is interesting too.
Oh, there's also this:
http://home.earthlink.net/~mrob/pub/perl/hypercalc.txt
It would be interesting to translate hypercalc into Lisp for comparison.
E.
In article <cf333042.04011...@posting.google.com>,
Gareth McCaughan
> pie...@lynxgeo.com (Pieter) wrote in message news:<8fb8b19a.04011...@posting.google.com>...
> > Joe Marshall <prunes...@comcast.net> wrote in message news:<brp418...@comcast.net>...
> >
> > > Have you estimated the depth of stack needed?
> >
> > I am not completely sure that I understand what you are asking. :( I
> > know that (ackerman 4 4)'s answer is HUGE and that the stack must be
> > VERY big. I know this because of other implimentations though.
>
> What makes you think that bignum integers are stored on the stack?
What makes you think he thinks that bignum integers are stored
on the stack?
--
Gareth McCaughan
.sig under construc
Michael Hudson
Isn't the Ackerman function one of those things that to estimate the
stack used by its computation you need to estimate the result?
Cheers,
mwh
--
Exam invigilation - it doesn't come much harder than that, esp if
the book you're reading turns out to be worse than expected.
-- Dirk Bruere, sci.physics.research
Joe Marshall
> Joe Marshall <j...@ccs.neu.edu> writes:
>
>> pie...@lynxgeo.com (Pieter) writes:
>>
>> > Joe Marshall <prunes...@comcast.net> wrote in message news:<brp418...@comcast.net>...
>> >
>> >> Have you estimated the depth of stack needed?
>> >
>> > I am not completely sure that I understand what you are asking. :( I
>> > know that (ackerman 4 4)'s answer is HUGE and that the stack must be
>> > VERY big. I know this because of other implimentations though.
>>
>> I'm just asking if you have an idea of exactly how big ``VERY big''
>> is. I think you have underestimated it.
>
> Isn't the Ackerman function one of those things that to estimate the
> stack used by its computation you need to estimate the result?
One shouldn't be afraid of recursion, especially when considering
Ackermann's function.
You can estimate the stack necessary for the single call to
(ackermann 4 4) without running the program.
--
~jrm
Pieter
> do you expect to happen?
More manners to start with...
In my mind I was testing the suitability for doing cryptographic (RSA)
programming with Lisp. I haven't worked with lisp before but I heard
about this feature called "bignum"'s i thought RSA might be easier in
it than in something like C. I thought using AckermanN (which is easy
enough to program in a new/unfamiliar language) would give a big
enough number to test this with. If it can handle ackermann then
Cryptography would be peanuts.
> Do you really think that the stack depth is all that stands in your
> way? The value you are trying to compute involves numbers like
>
> 65536
> 2
> 2
>
> have you tried evaluating (expt 2 (expt 2 65536))? On the same Lisp
> implementation that you are using, I get:
>
> *** overflow during multiplication of large numbers
> Skill testing question: in the straightforward binary representation,
> how many bits of storage would the number (expt 2 (expt 2 65536))
> require?
>
> Also, there are two N's in Ackermann, by the way.
back-of-the-envelope like: 3.1859808040601742833346296624825e+3946
I really see the point that you are making. I am not being difficult,
maybe uninformed.
Is it now required of me to impliment a /proper/ bignum package
(similar to the one which the GNU people implimented for C/C++ and is
used in GPG). And; How would I go about it?
Trying to use the result of (ackermann 4 4) IS NOT bright. Afterwards
I thought of testing it with some published prime numbers. (I think
they were in the order of 200 decimal digits) doing an exponent of two
of them:
(mod
(expt <200digits> <200digits>)
<200digits>
)
also gave me an overflow... I KNOW this number is (very) big too.
Would I then have to impliment a loop that does a multiplication, then
a mod, then a multiplication and then a mod (for RSA) to get the
factor of the two primes?
What I thought after hearing about bignums is that I can just about
chuck anything at it, and the Lisp interpreter (or compiler or
whatever) would handle this bignum on its own. Is this not so?
However. Thank you for your response which was quite informative.
Regards
Pieter
Joe Marshall
> In my mind I was testing the suitability for doing cryptographic (RSA)
> programming with Lisp. I haven't worked with lisp before but I heard
> about this feature called "bignum"'s I thought RSA might be easier in
> it than in something like C. I thought using AckermanN (which is easy
> enough to program in a new/unfamiliar language) would give a big
> enough number to test this with. If it can handle ackermann then
> Cryptography would be peanuts.
It definitely would.
The reason I was cryptic before is twofold: Ackermann's function is
often used in homework problems or in employment tests.
(See http://www.itasoftware.com/careers/programmers-archive.php)
The second reason is that figuring out (Ack 4 4) involves a lot of
interesting thinking. I got a kick out of it and I didn't want to
spoil it. (Gee, this is big...really big...DAMN!)
> back-of-the-envelope like: 3.1859808040601742833346296624825e+3946
Where did you get *that* envelope?
Actually, I think your estimate is a little low. The log of (ack 4 4)
has about 39400 digits.
> Is it now required of me to impliment a /proper/ bignum package
> (similar to the one which the GNU people implimented for C/C++ and is
> used in GPG). And; How would I go about it?
Lisp has a proper bignum package.
> Trying to use the result of (ackermann 4 4) IS NOT bright. Afterwards
> I thought of testing it with some published prime numbers. (I think
> they were in the order of 200 decimal digits) doing an exponent of two
> of them:
>
> (mod
> (expt <200digits> <200digits>)
> <200digits>
> )
>
> also gave me an overflow... I KNOW this number is (very) big too.
You got an overflow because (expt <200 digits> <200 digits>) won't fit
in the machine even though
(mod (expt <200 digits> <200 digits>) <200 digits>) will.
If you compute it like this, though:
(defun expmod (base exponent mod)
(cond ((zerop exponent) 1)
((evenp exponent) (mod (let ((x (expmod base (/ exponent 2) mod)))
(* x x))
mod))
(t (mod (* base (expmod base (1- exponent) mod))
mod))))
You'll have no problems.
(expmod 640785284696442065785559134003308932264708355179002798538113
671286301850793527622248679786362012411973295201562077406347
541607700526106309999871171548445806906603126622271198261079)
=> 184927654951560197998922671105024055618160643054333015564836
--
~jrm
Christophe Rhodes
> pie...@lynxgeo.com (Pieter) writes:
>
>> Trying to use the result of (ackermann 4 4) IS NOT bright. Afterwards
>> I thought of testing it with some published prime numbers. (I think
>> they were in the order of 200 decimal digits) doing an exponent of two
>> of them:
>>
>> (mod
>> (expt <200digits> <200digits>)
>> <200digits>
>> )
>>
>> also gave me an overflow... I KNOW this number is (very) big too.
>
> You got an overflow because (expt <200 digits> <200 digits>) won't fit
> in the machine even though
> (mod (expt <200 digits> <200 digits>) <200 digits>) will.
>
> If you compute it like this, though [... elided ...]
So as a quality of implementation issue, might it not be argued that
it would be good if implementations recognized the
(mod (expt ...) ...)
idiom, and compiled it to code that only overflows if it needs to?
Christophe
--
http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757
(set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b)))
(defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge)
Tim Bradshaw
>> 65536
>> 2
>> 2
> Is it now required of me to impliment a /proper/ bignum package
> (similar to the one which the GNU people implimented for C/C++ and is
> used in GPG). And; How would I go about it?
I think you haven't realised what this number means: you don't have
enough memory to represent it exactly.
Joe Marshall
> So as a quality of implementation issue, might it not be argued that
> it would be good if implementations recognized the
> (mod (expt ...) ...)
> idiom, and compiled it to code that only overflows if it needs to?
It *might* be, but that seems to me to be a rather `ad-hoc'
optimization. You only run into that pattern when doing number
theoretical stuff like RSA.
--
~jrm
Erann Gat
Of course you do, you just have to use a representation different from the
usual one. (In fact, that number is represented exactly in this very
post, and without knowing what kind of machine you're using to read this I
venture to say that this post is not coming anywhere close to exhausting
your available memory.)
See http://home.earthlink.net/~mrob/pub/perl/hypercalc.txt for an actual
implementation of a representation that can handle numbers vastly larger
than the one above.
E.
Tim Bradshaw
> Of course you do, you just have to use a representation different from the
> usual one.
Damn! I was going to add a caveat like that, I should have known I'd
need to (:-). I think what I
need is some kind of careful statement which comes down to `you don't
have enough memory to represent it exactly assuming you use some
obvious representation which is likely to be efficient for general
machine calculation and has been discovered and also no one is allowed
to disagree'.
> (In fact, that number is represented exactly in this very
> post, and without knowing what kind of machine you're using to read this I
> venture to say that this post is not coming anywhere close to exhausting
> your available memory.)
Now come on, surely you know I read news on a dodgy z80 connected via an
acoustic coupler at 1200/75. It doesn't take much to exhau$%^&*((((((((((((9(
NO CARRIER
Thomas F. Burdick
Wow, that's cool, but ... is anyone else disturbed by the fact that
this was implemented in a language where it's legal to add 12 to
"bannanas"?
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Adam Warner
>> See http://home.earthlink.net/~mrob/pub/perl/hypercalc.txt for an actual
>> implementation of a representation that can handle numbers vastly larger
>> than the one above.
>
> Wow, that's cool, but ... is anyone else disturbed by the fact that
> this was implemented in a language where it's legal to add 12 to
> "bannanas"?
I'm still disturbed by the fact that it's legal to add 12 hours to 12
metres in all our languages!
Have fun,
Adam
Jacek Generowicz
> Hi Thomas F. Burdick,
> >
> > Wow, that's cool, but ... is anyone else disturbed by the fact that
> > this was implemented in a language where it's legal to add 12 to
> > "bannanas"?
>
> I'm still disturbed by the fact that it's legal to add 12 hours to 12
> metres in all our languages!
It ain't "legal"[*] in my language:
[1]> (defgeneric add (a b))
#<GENERIC-FUNCTION ADD>
[2]> (defclass hours () ((n :initarg :n)))
#<STANDARD-CLASS HOURS>
[3]> (defclass metres () ((n :initarg :n)))
#<STANDARD-CLASS METRES>
[4]> (add (make-instance 'hours :n 12) (make-instance 'metres :n 12))
*** - NO-APPLICABLE-METHOD: When calling #<GENERIC-FUNCTION ADD> with arguments (#<HOURS #x203088A1> #<METRES #x2030A7CD>), no method is applicable.
1. Break [5]>
[*] Unless I decide that it should be, of course.
Erik Naggum
| I'm still disturbed by the fact that it's legal to add 12 hours to 12
| metres in all our languages!
So 12 p.m. really means «12 per meter»? Yay, I can make sense of the
Imperial ways, yet.
--
Erik Naggum | Oslo, Norway 2004-026
Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.
Duncan Rose
> * Adam Warner
> | I'm still disturbed by the fact that it's legal to add 12 hours to 12
> | metres in all our languages!
>
> So 12 p.m. really means «12 per meter»? Yay, I can make sense of the
> Imperial ways, yet.
As you mentioned in another thread, understanding the historic context of
(in that thread) the code is important (and can take a lot of time).
And so it is I think with Imperial measurements. Yes, they're lossage for
many things when compared to metric. But there are reasons for the way
they are (and I'm not saying the reasons are necessarily good ones!)
;-)
-Duncan
Arthur Lemmens
> I'm still disturbed by the fact that it's legal to add 12 hours to 12
> metres in all our languages!
I've written a library that can check for these kinds of 'unit errors'.
This has helped me a lot with implementing and verifying physics and
biology formulas.
Here's a small sample session with your example:
;; You can't add hours and meters.
UNITS 19 > (+ (quantity 12 'hour) (quantity 12 'meter))
Error: Unit mismatch between 43200 sec and 12 m.
1 (abort) Return to level 0.
2 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other options
UNITS 20 : 1 > :c 2
;; Multiplying hours and meters is no problem.
UNITS 21 > (* (quantity 12 'hour) (quantity 12 'meter))
518400 m sec
Here's a slightly more complicated session:
UNITS 16 > (defconstant +gas-constant+
(quantity 8.315 '(joule (mole -1) (kelvin -1))))
+GAS-CONSTANT+
UNITS 17 > (defun gas-pressure (gas-density temperature molecular-weight)
(check-units gas-density '(kg (m -3)))
(check-units temperature 'kelvin)
(check-units molecular-weight '(kg (mole -1)))
(check-units (/ (* gas-density +gas-constant+ temperature)
molecular-weight)
'pascal))
GAS-PRESSURE
UNITS 18 > (gas-pressure (quantity 2 '(kg (meter -3)))
(quantity 295 'kelvin)
(quantity 32 '(gram (mole -1))))
153307.81249999997 kg m-1 sec-2
UNITS 19 > (gas-pressure (quantity 2 '(kg (meter -1)))
(quantity 295 'kelvin)
(quantity 32 '(gram (mole -1))))
Error: The quantity 2 kg m-1 should have units (KG (M -3)).
1 (abort) Return to level 0.
2 Return to top loop level 0.
--
Arthur Lemmens