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

我在OS X的Guile 1.8.8口译员中练习Scheme。我注意到了一些有趣的东西。

这里的expt函数基本上是取幂expt(b,n) = b^n ：

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

如果我尝试一些input

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

这里来了奇怪的部分：

  > (expt 2 64) 0 

更奇怪的是，直到n=488它停留在0 ：

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

当我用repl.it在线解释器试试这个代码时，它按预期工作。 那么Guile到底怎么了 ？

（注：在某些方言中， remainder函数称为mod 。）

Answer 1

我最近修复了Guile 2.0中的这个bug。 当C编译器开始优化溢出检查时，这个错误就出现了，理论上如果发生了一个有符号的整数溢出，那么这个行为是不确定的，因此编译器可以做任何喜欢的事情。

Answer 2

我可以在OS X上重现与guile 2.0.6的问题。归结为：

 > (* 4294967296 4294967296) $1 = 0 

我的猜测是，guile使用本地inttypes来存储小数字，然后切换到一个bignums，由GNU MP支持，当本地整数太小。 也许在这种特殊情况下，检查失败，计算溢出本地int。

有趣的是，下面的循环显示2 ^ 32和2 ^ 60之间的2的平方幂导致0：

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

结果是：

 (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

我无法重现您运行Arch的结果。

这是我的terminal会话的日志：

 $ 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) (* xx)) guile> (define (even? x) (= (remainder x 2) 0)) guile> (define (expt bn) (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) guile> (exit)