derek5.
2013-01-24 07:01
采纳率: 100%
浏览 262
已采纳

Guile Scheme 解释器中奇怪的乘法行为

I was practicing Scheme in Guile 1.8.8 interpreter on OS X. I noticed something interesting.

Here's expt function which is basically does exponentiation expt(b,n) = b^n :

 (define (square x) (* x x))
 (define (even? x) (= (remainder x 2) 0))
 (define (expt b n) 
      (cond ((= n 0) 1)
        ((even? n) (square (expt b (/ n 2))))
        (else (* b (expt b (- n 1))))
      ))

If I try it with some inputs

 > (expt 2 10)
 1024
 > (expt 2 63)
 9223372036854775808

Here comes the strange part:

 > (expt 2 64)
 0

More strangely, until n=488 it stays at 0:

 > (expt 2 487)
 0
 > (expt 2 488)
 79916762888089401123.....
 > (expt 2 1000)
 1071508607186267320948425049060....
 > (expt 2 10000)
 0

When I try this code with repl.it online interpreter, it works as expected. So what the hell is wrong with Guile?

(Note: On some dialects, remainder function is called as mod.)

转载于:https://stackoverflow.com/questions/14495636/strange-multiplication-behavior-in-guile-scheme-interpreter

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • 10.24 2013-01-24 09:58
    已采纳

    I recently fixed this bug in Guile 2.0. The bug came into existence when C compilers started optimizing out overflow checks, on the theory that if a signed integer overflow occurs then the behavior is unspecified and thus the compiler can do whatever it likes.

    已采纳该答案
    评论
    解决 无用
    打赏 举报
  • ?yb? 2013-01-24 08:17

    I wasn't able to reproduce your results running Arch.

    Here is a log of my terminal session:

    $ uname -r
    3.6.10-1-ARCH
    $ guile --version
    Guile 1.8.8
    Copyright (c) 1995, 1996, 1997, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation
    Guile may be distributed under the terms of the GNU General Public Licence;
    certain other uses are permitted as well.  For details, see the file
    `COPYING', which is included in the Guile distribution.
    There is no warranty, to the extent permitted by law.
    $ guile
    guile> (define (square x) (* x x))
    guile> (define (even? x) (= (remainder x 2) 0))
    guile> (define (expt b n)
            (cond ((= n 0) 1)
                ((even? n) (square (expt b (/ n 2))))
                (else (* b (expt b (- n 1))))))
    guile> (expt 2 10)
    1024
    guile> (expt 2 64)
    18446744073709551616
    guile> (expt 2 487)
    399583814440447005616844445413525287135820562261116307309972090832047582568929999375399181192126972308457847183540047730617340886948900519205142528
    guile> (expt 2 488)
    799167628880894011233688890827050574271641124522232614619944181664095165137859998750798362384253944616915694367080095461234681773897801038410285056
    guile> (expt 2 1000)
    10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
    guile> (expt 2 10000)
    19950631168807583848837421626835850838234968318861924548520089498529438830221946631919961684036194597899331129423209124271556491349413781117593785932096323957855730046793794526765246551266059895520550086918193311542508608460618104685509074866089624888090489894838009253941633257850621568309473902556912388065225096643874441046759871626985453222868538161694315775629640762836880760732228535091641476183956381458969463899410840960536267821064621427333394036525565649530603142680234969400335934316651459297773279665775606172582031407994198179607378245683762280037302885487251900834464581454650557929601414833921615734588139257095379769119277800826957735674444123062018757836325502728323789270710373802866393031428133241401624195671690574061419654342324638801248856147305207431992259611796250130992860241708340807605932320161268492288496255841312844061536738951487114256315111089745514203313820202931640957596464756010405845841566072044962867016515061920631004186422275908670900574606417856951911456055068251250406007519842261898059237118054444788072906395242548339221982707404473162376760846613033778706039803413197133493654622700563169937455508241780972810983291314403571877524768509857276937926433221599399876886660808368837838027643282775172273657572744784112294389733810861607423253291974813120197604178281965697475898164531258434135959862784130128185406283476649088690521047580882615823961985770122407044330583075869039319604603404973156583208672105913300903752823415539745394397715257455290510212310947321610753474825740775273986348298498340756937955646638621874569499279016572103701364433135817214311791398222983845847334440270964182851005072927748364550578634501100852987812389473928699540834346158807043959118985815145779177143619698728131459483783202081474982171858011389071228250905826817436220577475921417653715687725614904582904992461028630081535583308130101987675856234343538955409175623400844887526162643568648833519463720377293240094456246923254350400678027273837755376406726898636241037491410966718557050759098100246789880178271925953381282421954028302759408448955014676668389697996886241636313376393903373455801407636741877711055384225739499110186468219696581651485130494222369947714763069155468217682876200362777257723781365331611196811280792669481887201298643660768551639860534602297871557517947385246369446923087894265948217008051120322365496288169035739121368338393591756418733850510970271613915439590991598154654417336311656936031122249937969999226781732358023111862644575299135758175008199839236284615249881088960232244362173771618086357015468484058622329792853875623486556440536962622018963571028812361567512543338303270029097668650568557157505516727518899194129711337690149916181315171544007728650573189557450920330185304847113818315407324053319038462084036421763703911550639789000742853672196280903477974533320468368795868580237952218629120080742819551317948157624448298518461509704888027274721574688131594750409732115080498190455803416826949787141316063210686391511681774304792596709376
    guile> (exit)
    
    评论
    解决 无用
    打赏 举报
  • python小菜 2013-01-24 08:25

    I could reproduce the problem with guile 2.0.6 on OS X. It boils down to:

    > (* 4294967296 4294967296)
    $1 = 0
    

    My guess is that guile uses the native int type to store small numbers, and then switches to a bignums, backed by GNU MP when the native ints are too small. Maybe in that particular case, the check fails, and the computation overflows the native int.

    Interestingly, the following loop shows that squaring powers of two between 2^32 and 2^60 results in 0:

    (let loop
        ((x 1)
         (exp 0))
      (format #t "(2^~s) ^ 2 = ~s\n" exp (* x x))
      (if (< exp 100)
          (loop (* 2 x) (+ 1 exp))))
    

    Results in:

    (2^0) ^ 2 = 1
    (2^1) ^ 2 = 4
    (2^2) ^ 2 = 16
    (2^3) ^ 2 = 64
    (2^4) ^ 2 = 256
    (2^5) ^ 2 = 1024
    (2^6) ^ 2 = 4096
    (2^7) ^ 2 = 16384
    (2^8) ^ 2 = 65536
    (2^9) ^ 2 = 262144
    (2^10) ^ 2 = 1048576
    (2^11) ^ 2 = 4194304
    (2^12) ^ 2 = 16777216
    (2^13) ^ 2 = 67108864
    (2^14) ^ 2 = 268435456
    (2^15) ^ 2 = 1073741824
    (2^16) ^ 2 = 4294967296
    (2^17) ^ 2 = 17179869184
    (2^18) ^ 2 = 68719476736
    (2^19) ^ 2 = 274877906944
    (2^20) ^ 2 = 1099511627776
    (2^21) ^ 2 = 4398046511104
    (2^22) ^ 2 = 17592186044416
    (2^23) ^ 2 = 70368744177664
    (2^24) ^ 2 = 281474976710656
    (2^25) ^ 2 = 1125899906842624
    (2^26) ^ 2 = 4503599627370496
    (2^27) ^ 2 = 18014398509481984
    (2^28) ^ 2 = 72057594037927936
    (2^29) ^ 2 = 288230376151711744
    (2^30) ^ 2 = 1152921504606846976
    (2^31) ^ 2 = 4611686018427387904
    (2^32) ^ 2 = 0
    (2^33) ^ 2 = 0
    (2^34) ^ 2 = 0
    (2^35) ^ 2 = 0
    (2^36) ^ 2 = 0
    (2^37) ^ 2 = 0
    (2^38) ^ 2 = 0
    (2^39) ^ 2 = 0
    (2^40) ^ 2 = 0
    (2^41) ^ 2 = 0
    (2^42) ^ 2 = 0
    (2^43) ^ 2 = 0
    (2^44) ^ 2 = 0
    (2^45) ^ 2 = 0
    (2^46) ^ 2 = 0
    (2^47) ^ 2 = 0
    (2^48) ^ 2 = 0
    (2^49) ^ 2 = 0
    (2^50) ^ 2 = 0
    (2^51) ^ 2 = 0
    (2^52) ^ 2 = 0
    (2^53) ^ 2 = 0
    (2^54) ^ 2 = 0
    (2^55) ^ 2 = 0
    (2^56) ^ 2 = 0
    (2^57) ^ 2 = 0
    (2^58) ^ 2 = 0
    (2^59) ^ 2 = 0
    (2^60) ^ 2 = 0
    (2^61) ^ 2 = 5316911983139663491615228241121378304
    (2^62) ^ 2 = 21267647932558653966460912964485513216
    (2^63) ^ 2 = 85070591730234615865843651857942052864
    (2^64) ^ 2 = 340282366920938463463374607431768211456
    (2^65) ^ 2 = 1361129467683753853853498429727072845824
    (2^66) ^ 2 = 5444517870735015415413993718908291383296
    (2^67) ^ 2 = 21778071482940061661655974875633165533184
    (2^68) ^ 2 = 87112285931760246646623899502532662132736
    (2^69) ^ 2 = 348449143727040986586495598010130648530944
    (2^70) ^ 2 = 1393796574908163946345982392040522594123776
    (2^71) ^ 2 = 5575186299632655785383929568162090376495104
    (2^72) ^ 2 = 22300745198530623141535718272648361505980416
    (2^73) ^ 2 = 89202980794122492566142873090593446023921664
    (2^74) ^ 2 = 356811923176489970264571492362373784095686656
    (2^75) ^ 2 = 1427247692705959881058285969449495136382746624
    (2^76) ^ 2 = 5708990770823839524233143877797980545530986496
    (2^77) ^ 2 = 22835963083295358096932575511191922182123945984
    (2^78) ^ 2 = 91343852333181432387730302044767688728495783936
    (2^79) ^ 2 = 365375409332725729550921208179070754913983135744
    (2^80) ^ 2 = 1461501637330902918203684832716283019655932542976
    (2^81) ^ 2 = 5846006549323611672814739330865132078623730171904
    (2^82) ^ 2 = 23384026197294446691258957323460528314494920687616
    (2^83) ^ 2 = 93536104789177786765035829293842113257979682750464
    (2^84) ^ 2 = 374144419156711147060143317175368453031918731001856
    (2^85) ^ 2 = 1496577676626844588240573268701473812127674924007424
    (2^86) ^ 2 = 5986310706507378352962293074805895248510699696029696
    (2^87) ^ 2 = 23945242826029513411849172299223580994042798784118784
    (2^88) ^ 2 = 95780971304118053647396689196894323976171195136475136
    (2^89) ^ 2 = 383123885216472214589586756787577295904684780545900544
    (2^90) ^ 2 = 1532495540865888858358347027150309183618739122183602176
    (2^91) ^ 2 = 6129982163463555433433388108601236734474956488734408704
    (2^92) ^ 2 = 24519928653854221733733552434404946937899825954937634816
    (2^93) ^ 2 = 98079714615416886934934209737619787751599303819750539264
    (2^94) ^ 2 = 392318858461667547739736838950479151006397215279002157056
    (2^95) ^ 2 = 1569275433846670190958947355801916604025588861116008628224
    (2^96) ^ 2 = 6277101735386680763835789423207666416102355444464034512896
    (2^97) ^ 2 = 25108406941546723055343157692830665664409421777856138051584
    (2^98) ^ 2 = 100433627766186892221372630771322662657637687111424552206336
    (2^99) ^ 2 = 401734511064747568885490523085290650630550748445698208825344
    (2^100) ^ 2 = 1606938044258990275541962092341162602522202993782792835301376
    
    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题