P(65536**(1<<29)) stalls

Yusuke_ENDOH · July 17, 2007, 3:33pm

e$B1sF#$H?=$7$^$9!#e(B

e$B0J2<$N$h$&$K$9$k$HH?1~$,$J$/$J$j$^$9!#e(BCtrl+C
e$B$G$b;_$a$i$l$^$;$s!#e(B

$ ./ruby -ve ‘p(65536**(1<<29))’
ruby 1.8.6 (2007-07-17 patchlevel 5000) [i686-linux]

$ ./ruby -ve ‘p(65536**(1<<29))’
ruby 1.9.0 (2007-07-17 patchlevel 0) [i686-linux]

bignum e$B$NBg$-$5$N%A%’%C%/$Ge(B integer overflow
e$B$7$F$$$k$N$,860x$N$h$&$G$9!#e(B
1.8 e$B$G$N1~5^A<CV$G$9!#e(B

Index: bignum.c

— bignum.c (revision 12809)
+++ bignum.c (working copy)
@@ -1755,8 +1755,13 @@
if (yy > 0) {
VALUE z = 0;
long mask;

      VALUE f = 1, t1 = RBIGNUM(x)->len * SIZEOF_BDIGITS;

      if (t1 / SIZEOF_BDIGITS == RBIGNUM(x)->len && t1 %

SIZEOF_BDIGITS == 0) {

```
          VALUE t2 = t1 * yy;
```

          if (t2 / yy == t1 && t2 % yy == 0 && t2 <= 1024*1024) f

= 0;

```
      }
```

      if (RBIGNUM(x)->len * SIZEOF_BDIGITS * yy > 1024*1024) {

      if (f) {
          rb_warn("in a**b, b may be too big");
          d = (double)yy;
          break;

1024*1024 e$B$,B(CM$GKd$a9~$^$l$F$$$k$N$,5$;}$A0-$$$s$G$9$,!"e(B
bignum e$B$N:GBgCM$C$F$A$c$s$H7h$^$C$F$J$$$s$G$7$g$&$+!#e(B

e$B$D$$$G$K!"=EH"$N6y$G$9$,!"0J2<$N;EMMJQ99$O0U?^$5$l$?$b$N$G$7$g$&$+!#e(B

$ ./ruby -ve ‘p(0**(1<<30))’
ruby 1.8.6 (2007-06-07 patchlevel 36) [i686-linux]
-e:1: warning: in a**b, b may be too big
0.0

$ ./ruby -ve ‘p(0**(1<<30))’
ruby 1.8.6 (2007-07-17 patchlevel 5000) [i686-linux]
0

Yusuke_ENDOH · July 18, 2007, 10:06am

e$B$J$+$@$G$9!#e(B

At Tue, 17 Jul 2007 22:30:38 +0900,
Yusuke ENDOH wrote in [ruby-dev:31242]:

bignum e$B$NBg$-$5$N%A%’%C%/$Ge(B integer overflow e$B$7$F$$$k$N$,860x$N$h$&$G$9!#e(B
1.8 e$B$G$N1~5^A<CV$G$9!#e(B

e$B$"$j$,$H$&$4$6$$$^$9!#$A$g$C$H0c$&7A$G$9$,!"%A%’%C%/$rD>$7$^$7$?!#e(B

1024*1024 e$B$,B(CM$GKd$a9~$^$l$F$$$k$N$,5$;}$A0-$$$s$G$9$,!"e(B
bignum e$B$N:GBgCM$C$F$A$c$s$H7h$^$C$F$J$$$s$G$7$g$&$+!#e(B

e$B$H$/$K7h$^$C$F$J$$$G$9!#:#$N$H$3$m!V%a%b%j$N5v$98B$j!W$H$$$&@)e(B
e$B8B$@$1$J$s$G$9$,!"$I$3$+$KL@<(E*$J@~0z$-$r$7$?$[$&$,$$$$$G$7$ge(B
e$B$&$+$M$’!#e(B

e$B$D$$$G$K!"=EH"$N6y$G$9$,!"0J2<$N;EMMJQ99$O0U?^$5$l$?$b$N$G$7$g$&$+!#e(B

$ ./ruby -ve ‘p(0**(1<<30))’
ruby 1.8.6 (2007-06-07 patchlevel 36) [i686-linux]
-e:1: warning: in a**b, b may be too big
0.0

$ ./ruby -ve ‘p(0**(1<<30))’
ruby 1.8.6 (2007-07-17 patchlevel 5000) [i686-linux]
0

0**((1<<30)-1)e$B$^$G$Oe(BFixnume$B$,JV$C$FMh$F$$$k$N$G!“F1$8e(B0e$B$,JV$k$[$&e(B
e$B$,0l4S@-$O$”$k$H;W$$$^$9$,!#e(B

Yusuke_ENDOH · July 18, 2007, 1:59pm

e$B1sF#$G$9!#e(B

e$B$A$g$C$H0c$&7A$G$9$,!"%A%’%C%/$rD>$7$^$7$?!#e(B

e$B=$@53NG’$7$^$7$?!#$J$k$[$I$=$&D>$;$P$$$$$N$+!D!D!#e(B

1024*1024 e$B$,B(CM$GKd$a9~$^$l$F$$$k$N$,5$;}$A0-$$$s$G$9$,!"e(B
bignum e$B$N:GBgCM$C$F$A$c$s$H7h$^$C$F$J$$$s$G$7$g$&$+!#e(B

e$B$H$/$K7h$^$C$F$J$$$G$9!#:#$N$H$3$m!V%a%b%j$N5v$98B$j!W$H$$$&@)e(B
e$B8B$@$1$J$s$G$9$,!"$I$3$+$KL@<(E*$J@~0z$-$r$7$?$[$&$,$$$$$G$7$ge(B
e$B$&$+$M$’!#e(B

e$B;d$b!V%a%b%j$N5v$98B$j!W$@$H;W$C$F$$$?$N$G!"Bg$-$9$.$ke(B Bignum
e$B$,e(B
Float e$B$K$J$k$HCN$C$F6C$-$^$7$?!#$I$3$+$K=q$$$F$^$7$?$C$1!#e(B

0**((1<<30)-1)e$B$^$G$Oe(BFixnume$B$,JV$C$FMh$F$$$k$N$G!“F1$8e(B0e$B$,JV$k$[$&e(B
e$B$,0l4S@-$O$”$k$H;W$$$^$9$,!#e(B

e$B$=$l$r8@$&$J$i!"!Ve(Bn**(1<<30) e$B$Oe(B 0 e$B$He(B 1 e$B0J30$Ne(B n
e$B$KBP$7$Fe(B Float e$B$rJV$9e(B
e$B$N$G!“e(B0 e$B$He(B 1 e$B$be(B Float
e$B$rJV$9$[$&$,0l4S@-$,$”$k!W$H$$$&5DO@$b@.$jN)$De(B
e$B5$$,$7$^$9!#$1$l$I!"$3$N5sF0$K0MB8$9$k%3!<%I$r=q$/;v$O$J$5$=$&$G$9$7!“e(B
e$B8D?ME*$K$bFC$K$3$@$o$j$O$J$$$N$G!”%(%s%P%0$G$J$$$J$i$=$l$G$$$$$G$9!#e(B

Yusuke_ENDOH · July 18, 2007, 3:19pm

e$B1sF#$G$9!#e(B

07/07/18 e$B$Ke(B U.Nakamura[email protected]
e$B$5$s$O=q$-$^$7$?e(B:

|
| e$B;d$b!V%a%b%j$N5v$98B$j!W$@$H;W$C$F$$$?$N$G!"Bg$-$9$.$ke(B Bignum e$B$,e(B
| Float e$B$K$J$k$HCN$C$F6C$-$^$7$?!#$I$3$+$K=q$$$F$^$7$?$C$1!#e(B

e$BBg$-$9$.$ke(BBignume$B$,e(BFloate$B$K$J$k!“$o$1$8$c$J$/$F!“e(BBignum#**e$B$N5se(B
e$BF0$H$7$F7k2L$,e(BFloate$B$K$J$k$3$H$b$”$k$h!”$H$$$&$3$H$@$H;W$$$^$9!#e(B

e$B$J$k$[$I!"0lHLE*$J%]%j%7!<$G$O$J$/e(B Bignum#**
e$B8GM-$N;EMM$J$s$G$9$M!#e(B

e$B7k2L$,e(BFloate$B$K$J$j$&$k$3$H$Oe(Brdoce$B$K=q$$$F$"$j$^$9$M!#e(B

http://www.ruby-lang.org/ja/man/index.cgi?cmd=view;name=Integer
e$B$Ne(B self ** other e$B$N$H$3$@$18+$F$^$7$?!#e(B

http://ruby-doc.org/core/classes/Bignum.html#M001127

The result may be a Fixnum, Bignum, or Float
e$B$N$3$H$G$7$g$&$+!#3N$+$K=q$$$F$“$k$C$A$c$”$j$^$9$,!“Nc$r$”$o$;8+$F!"e(B
e$B!Ve(BBignum ** Bignum e$B$G$be(B Float
e$B$K$J$j$&$k!W$H8+H4$/$N$O87$7$$$+$b!#e(B
e$B$;$a$F!"e(B

123456789 ** 123456789 #=> Infinity

e$B$rDI2C$7$F$b$i$($l$P!D!De(B (e$B$+$($C$F:.Mp$7$=$&e(B) e$B!#e(B

Yusuke_ENDOH · July 18, 2007, 4:57pm

e$B$^$D$b$He(B e$B$f$-$R$m$G$9e(B

In message “Re: [ruby-dev:31242] p(65536**(1<<29)) stalls”
on Tue, 17 Jul 2007 22:30:38 +0900, “Yusuke ENDOH” [email protected]
writes:

|1024*1024 e$B$,B(CM$GKd$a9~$^$l$F$$$k$N$,5$;}$A0-$$$s$G$9$,!"e(B
|bignum e$B$N:GBgCM$C$F$A$c$s$H7h$^$C$F$J$$$s$G$7$g$&$+!#e(B

e$BCfED$5$s$+$i$b$“$j$^$7$?$,!”%a%b%j$,5v$98B$j$NBg$-$5$N?tCM$re(B
e$B5v$9$H$$$&$N$,0l1~$N;EMM$G$9!#$Y$->h$N7W;;$N>l9g!“$”$kDxEY0Je(B
e$B>eBg$-$$?t$OIbF0>.?tE@1i;;$G6a;w$9$k$H$$$&<j$r;H$C$F$$$^$9!#e(B
e$B$9$0$Ke(BInfinitye$B$K$J$C$A$c$$$^$9$,!#e(B

e$B$O$$!#$^$:$$%1!<%9$,$"$l$P65$($F$/$@$5$$!#e(B

Yusuke_ENDOH · July 18, 2007, 2:13pm

e$B$3$s$K$A$O!"$J$+$`$ie(B(e$B$&e(B)e$B$G$9!#e(B

In message “[ruby-dev:31250] Re: p(65536**(1<<29)) stalls”
on Jul.18,2007 20:57:30, [email protected] wrote:
| > > 10241024 e$B$,B(CM$GKd$a9~$^$l$F$$$k$N$,5$;}$A0-$$$s$G$9$,!“e(B
| > > bignum e$B$N:GBgCM$C$F$A$c$s$H7h$^$C$F$J$$$s$G$7$g$&$+!#e(B
| >
| > e$B$H$/$K7h$^$C$F$J$$$G$9!#:#$N$H$3$m!V%a%b%j$N5v$98B$j!W$H$$$&@)e(B
| > e$B8B$@$1$J$s$G$9$,!”$I$3$+$KL@<(E$J@~0z$-$r$7$?$[$&$,$$$$$G$7$ge(B
| > e$B$&$+$M$'!#e(B
|
| e$B;d$b!V%a%b%j$N5v$98B$j!W$@$H;W$C$F$$$?$N$G!"Bg$-$9$.$ke(B Bignum e$B$,e(B
| Float e$B$K$J$k$HCN$C$F6C$-$^$7$?!#$I$3$+$K=q$$$F$^$7$?$C$1!#e(B

e$BBg$-$9$.$ke(BBignume$B$,e(BFloate$B$K$J$k!“$o$1$8$c$J$/$F!“e(BBignum#**e$B$N5se(B
e$BF0$H$7$F7k2L$,e(BFloate$B$K$J$k$3$H$b$”$k$h!”$H$$$&$3$H$@$H;W$$$^$9!#e(B
e$B7k2L$,e(BFloate$B$K$J$j$&$k$3$H$Oe(Brdoce$B$K=q$$$F$"$j$^$9$M!#e(B

e$B$I$&$$$&4p=`$Ge(BFloate$B$K$J$k$+!“$H$$$&$N$O$”$C$F$b$$$$$N$+$b$7$le(B
e$B$J$$$H$O;W$$$^$9!#e(B

e$B$=$l$G$O!#e(B