38

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

ahmet alp balkan
  • 42,679
  • 38
  • 138
  • 214
  • How come you had (expt 2 64) two times and the first time it was 0, and then it wasn't (79916762888089401123.....) – malkia Jan 24 '13 at 08:16
  • Try renaming your `expt` to `my-expt`. Just to rule out any confusion over whether the problem is your `expt` or the builtin `expt`. – soegaard Jan 24 '13 at 08:23
  • Normally `remainder` and `modulo` works differently for negative numbers. – soegaard Jan 24 '13 at 08:23
  • Your code computes (expt 2 488) as the square of (expt 2 244). Since (expt 2 488) isn't being reported as zero, I'd bet at pretty hefty odds that what you're seeing is an oddity in *display* rather than in *computation*. What happens if you ask for something like (zerop (expt 2 100))? – Gareth McCaughan Jan 24 '13 at 09:36
  • Further information in case it's useful: I just tried this in guile 1.8.8 on an x64 box running FreeBSD and everything worked just fine. ahmet alp balkan, is your machine 64-bit? (Most recent Macs are.) If so, maybe the problem is somehow specific to OS X. – Gareth McCaughan Jan 24 '13 at 09:41
  • It looks as if guile's bignum-printing code is a very thin wrapper around GMP's mpz_get_str, which in turn is a very thin wrapper around GMP's mpn_get_str, which is rather complicated and does different things for numbers of different sizes. So that'd be my first guess at where any problem is likely to live. – Gareth McCaughan Jan 24 '13 at 09:56
  • Wouldn't it be better to report this as a bug on the [Guile bugtracker](http://savannah.gnu.org/bugs/?group=guile), rather than ask a question about it here? – Confusion Jan 24 '13 at 10:25
  • On my 64-bit MacPorts guile 1.8.8 on MacOS 10.6.8, it works fine. – gpvos Jan 24 '13 at 21:19
  • So I got hold of a Mac running Guile (actually version 1.6.8), and on that system (expt 2 488) is reported as zero ... and so is (expt 2 244), but (expt 2 122) is not. So, I'm going to guess that ahmed alp balkan's original report was in error, and it wasn't really giving zeros all the way from 64 to 487. And, accordingly, I now agree that it's a multiplication bug and not a number-to-string conversion bug. – Gareth McCaughan Jan 25 '13 at 17:16
  • The one in the original post, obviously. – Gareth McCaughan Jan 25 '13 at 23:46

3 Answers3

36

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.

Joey
  • 344,408
  • 85
  • 689
  • 683
Mark H Weaver
  • 491
  • 4
  • 2
  • Mark, just to clarify, do you mean you've verified that that bug was the cause of the problem here? – Gareth McCaughan Jan 24 '13 at 10:03
  • The reason I ask is that it seems like a bug in Guile's multiplication couldn't actually cause these symptoms (unless it depended on the depth of the call stack, or involved uninitialized memory, or something like that -- which isn't the case for the bug you fixed). Because (expt 2 488) is calculated by doing (expt 2 244) and squaring the result -- so if (expt 2 244) is truly returning zero, how can (expt 2 488) give the right (bignum) answer? – Gareth McCaughan Jan 24 '13 at 10:07
  • Do we know for sure that (expt 2 244) returned 0? Could someone please confirm this? If it were the case, then I would agree with Gareth that the bug is most likely in number->string. For bignums Guile uses GNU MP's mpz_get_str, so if it's a bignum display bug, I'd be curious to see the results of "make check" for the version of GNU MP on Homebrew. It would also be worthwhile to try compiling both GNU MP and Guile with -fwrapv. – Mark H Weaver Jan 25 '13 at 03:05
  • Here comes the hero! Thanks! – ahmet alp balkan Jan 25 '13 at 05:46
  • I observed this bad behavior in a very simple statement like `(* 10000 100000000000000000000000)`. – ahmet alp balkan Jan 25 '13 at 06:22
  • ahmet alp balkan, what exactly did you see when you did that? And, in cases where you've got something that (apparently) spuriously returns zero, what happens if you explicitly test with `zero?`? If the problem is in converting numbers to strings rather than in calculating them, then `zero?` should return false even though the number is being displayed as zero. – Gareth McCaughan Jan 25 '13 at 15:56
  • OK, so after doing some tests myself I now think that the original poster's report was incorrect; there are intermediate values between 64 and 488 that produce nonzero values; and indeed the problem is with multiplication rather than with conversion from numbers to strings. In which case, this probably is the same bug that Mark fixed. Thanks, Mark! – Gareth McCaughan Jan 25 '13 at 17:17
11

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
Thomas
  • 10,358
  • 4
  • 27
  • 35
  • Then why does 2^488 work correctly but nothing in 2^(64..487) range? 2^65 does not work as well, that could be because 2^64 is interpreted as 0, but what does change at 2^488? – ahmet alp balkan Jan 24 '13 at 08:41
  • Also, `(* 4294967297 4294967295)` gives -1, `(* 4294967296 4294967295)` gives -4294967296 and `(* 4294967297 4294967297)` gives 8589934593. That's on Guile 1.8.8 from Homebrew. – Lloeki Jan 24 '13 at 09:26
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)
cmt
  • 1,475
  • 9
  • 11