=1B$B$`$i$?$G$9!#=1B(B

Bignum#* =1B$B$r=1B(B Toom3 =1B$B>hK!=1B(B (r=3D2 =1B$B$N=1B(B Toom-Cook =
=1B$B>hK!=1B(B) =1B$B$KBP1~$5$;$k=1B(B patch =1B$B$r:n$j$^$7$?!#=1B(B
svn trunk =1B$B$N=1B(B r29883 =1B$B$r%Y!<%9$K3+H/$7$F$$$^$7$?$,!"=1B(Br299=
65 =1B$B$K$bE,MQ2DG=3D$G$7$?!#=1B(B
patch =1B$B$O0J2<$N=1B(B gist =1B$B$KEj9F$7$F$"$j$^$9!#=1B(B
https://gist.github.com/726653

n =1B$B%S%C%H?tF1;N$N>h;;=1B(B10=1B$B2sJ,$N7W;;;~4V$r=1B(B 1.9.2p80 =
=1B$B$HHf3S$9$k$H0J2<$N$h$&$K$J$j$^$9!#=1B(B
=
1=1B$B@iK|%S%C%H?tF1;N$N>h;;$K$*$$$F=1B(B2=1B$BG\6/$N9bB.2=3D$,<B8=3D$G$-$=
F$$$^$9!#=1B(B

  ------------------------------------------
      n [bit]   1.9.2p80 [sec]   Toom3 [sec]
  ------------------------------------------
            1                0             0
      100_000             0.04          0.04
      500_000             0.44          0.36
    1_000_000             1.33          0.88
    5_000_000            18.98         11.28
   10_000_000            60.50         28.82
   50_000_000           705.13        332.78
  100_000_000          2119.45        946.28
  ------------------------------------------

=1B$B;HMQ$7$?%^%7%s$N%9%Z%C%/$O0J2<$N$H$*$j$G$9!#=1B(B
OS: Mac OS X 10.6.5
CPU: Core i7 2.66GHz
MEM: 8GB

=1B$B$3$N=1B(B patch =1B$B$G$O=1B(B Karatsuba =
=1B$B>hK!$+$i@Z$jBX$($k7e?t$NogCM=1B(B TOOM3_MUL_DIGITS =
=1B$B$r=1B(B150=1B$B$K=1B(B
=1B$B@_Dj$7$F$$$^$9!#$3$NCM$,:GE,$+$I$&$+$O$3$l$+$iD4::$7$^$9!#=1B(B

Toom3 =
=1B$B>hK!$KBP1~$5$;$F>h;;$,9bB.2=3D$5$l$k$3$H$G!"=3D|;;$HQQ>h$,4V@\E*$K9bB=
.2=3D$5$l$^$9!#=1B(B
=1B$B$9$k$H!"=1B(BRational =1B$B$,FbIt$G9T$C$F$kDLJ,$d!"=1B(Bprime.rb =
=1B$B$G<BAu$5$l$F$$$kAG0x?tJ,2r$J$I$N=1B(B
=1B$B9bB.2=3D$r<B8=3D$G$-$^$9!#=1B(B

=1B$B>e$N=1B(B patch =1B$B$K$O%G%P%C%0MQ$N%3!<%I$,:.$6$C$F$k$N$G!"=1B(B
=1B$B<h$j9~$s$GNI$1$l$P!"$=3D$l$i$r>C$7$?=1B(B patch =
=1B$B$r%^!<%8$7$F%3%_%C%H$7$?$$$G$9!#=1B(B

=1B$B$48!F$$7$F$$$?$@$1$^$9$G$7$g$&$+!#=1B(B

--=20
Kenta Murata
OpenPGP FP =3D 1D69 ADDE 081C 9CC2 2E54  98C1 CEFE 8AFB 6081 B062

=1B$BK\$r=3Dq$-$^$7$?=1B(B!!
=1B$B!X=1B(BRuby =1B$B5U0z$-%l%7%T!Y=1B(B =
http://www.amazon.co.jp/dp/4798119881/mrkn-22

E-mail: mrkn / mrkn.jp
twitter: http://twitter.com/mrkn/
blog: http://d.hatena.ne.jp/mrkn/