Comportement de multiplication étrange dans l'interpréteur Guile Scheme

Question

Je pratiquais Régime en Guile 1.8.8 interprète sur OS X. j'ai remarqué quelque chose d'intéressant.

Voici expt fonction de ce qui est fait de l'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))))
      ))

Si je l'ai essayer avec certaines entrées

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

Voici la partie étrange:

 > (expt 2 64)
 0

Plus étrangement, jusqu' n=488 il reste à 0:

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

Quand j'ai essayer ce code avec repl.il interprète en ligne, il fonctionne comme prévu. Donc, ce que l'enfer est le problème avec Guile?

(Remarque: Sur certains dialectes, remainder fonction est appelée en tant que mod.)

Answer 1

J'ai récemment corrigé ce bug dans Guile 2.0. Le bogue est apparu lorsque les compilateurs C ont commencé à optimiser les contrôles de débordement, en partant du principe que si un débordement d'entier signé se produit, le comportement n'est pas spécifié et le compilateur peut donc faire ce qu'il veut.

Answer 2

J'ai pu reproduire le problème avec guile 2.0.6 sur OS X. Il se résume à:

> (* 4294967296 4294967296)
$1 = 0

Ma conjecture est que ruse utilise le natif de type int pour stocker de petits nombres, et passe ensuite à une bignums, soutenu par GNU MP lorsque le natif ints sont trop petites. Peut-être que dans ce cas particulier, la vérification échoue, et le calcul des dépassements de la native int.

Fait intéressant, la boucle suivante montre que la quadrature des puissances de deux entre les 2^32 et 2^60 résultats en 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))))

Résultats:

(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

Je n'ai pas pu reproduire vos résultats avec Arch.

Voici un journal de ma session de 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) (* 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)