Strange multiplication behavior in Guile Scheme interpreter

Question

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.)

Answer 1

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.

Answer 2

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

Answer 3

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)