Bignum#to_s $B$N(B Karatsuba $B4p?tJQ49$K$h$k9bB.2=(B

[Kenta_M]

むらけんです．

まつもとさんの日記で話題になっていた Bignum#to_s の
Karatsuba 基数変換による高速化を C で実装してみました．
ベキ数のキャッシュアルゴリズムが少し変な気がしますが，パッチを添付します．

一応，添付した test_karatsuba.rb でテストもして，きちんと動いているようです．

処理速度的には，べき乗の演算時間が含まれていますが 1/4 以下になりました．
$ time ./ruby -e ‘p((65536**65536).to_s_orig(10))’ > r1.txt

real 4m6.110s
user 1m1.368s
sys 0m0.016s
$ time ./ruby -e ‘p((65536**65536).to_s(10))’ > r2.txt

real 0m41.312s
user 0m11.421s
sys 0m0.012s

[Kenta_M]

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

In message “Re: [ruby-dev:31323] Bignum#to_s e$B$Ne(B Karatsuba
e$B4p?tJQ49$K$h$k9bB.2=e(B”
on Wed, 1 Aug 2007 15:21:34 +0900, “Kenta M.”
[email protected] writes:
|
|[1 <text/plain; ISO-2022-JP (7bit)>]
|e$B$$i$1$s$G$9!%e(B | |e$B$^$D$b$H$5$s$NF|5-$GOCBj$K$J$C$F$$$?e(B Bignum#to_s e$B$Ne(B |Karatsuba e$B4p?tJQ49$K$h$k9bB.2=$re(B C e$B$G<BAu$7$F$_$^$7$?!%e(B |e$B%Y%-?t$N%-%c%C%7%e%"%k%4%j%:%$,>/$7JQ$J5$$,$7$^$9$,!$%Q%C%A$rE:IU$7$^$9!%e(B
|
|e$B0l1~!$E:IU$7$?e(B test_karatsuba.rb e$B$G%F%9%H$b$7$F!$$-$A$s$HF0$$$F$$$k$h$&$G$9!%e(B

e$B$A$g$&$Ie(B[ruby-dev:31312]e$B$r<h$j9~$b$&$H;W$C$F$$$?Lp@h$@$C$?$Ne(B
e$B$G$9$,!“$I$C$A$,$$$$$G$9$+$M$(!#$”$H!“e(BKaratsubae$B$H$$$($P$+$1;;e(B
e$B$N9bB.2=$K$D$$$F$be(B(e$B%”%k%4%j%:%`$,M}2r$G$-$:e(B)e$B$[$C$?$i$+$7$@$Ce(B
e$B$?$s$G$9$h$M$(!#e(B

[Kenta_M]

むらけんです．

私のところに ruby-dev:31312 が届いてないのが不思議・・・

On 8/1/07, Yukihiro M. [email protected] wrote:

まつもと ゆきひろです
ちょうど[ruby-dev:31312]を取り込もうと思っていた矢先だったの
ですが、どっちがいいですかねえ。

同じ条件で処理時間を計測して，短い方を採用したらいいと思いました．
そこで，添付のようなパッチと，ベンチマークプログラムで計測したところ
以下のようになりました．

$ ./ruby -I lib karatsuba.rb
Rehearsal --------------------------------------------------
original 2.410000 0.000000 2.410000 ( 9.625259)
ruby-dev:31312 2.420000 0.000000 2.420000 ( 9.635740)
ruby-dev:31323 1.740000 0.000000 1.740000 ( 6.842046)
----------------------------------------- total: 6.570000sec

                user     system      total        real

original 2.420000 0.000000 2.420000 ( 9.931306)
ruby-dev:31312 2.420000 0.000000 2.420000 ( 9.627448)
ruby-dev:31323 1.740000 0.000000 1.740000 ( 6.842890)

なぜか ruby-dev:31312 が，オリジナルと比較して早くなってないのですが，
ベンチマークプログラムが悪いのでしょうか・・・
単純に[ruby-dev:31312] が速くなる条件と，私の [ruby-dev:31323] が
速くなる条件が違うという理解で良いものかどうか．

åŠ ãˆã¦ï¼Œ[ruby-dev:31323] で添付した私のパッチはバグがある状態のものでした．
正しくは，

+VALUE
+rb_big2str_karatsuba(VALUE x, VALUE base)
+{

• return rb_big2str0_karatsuba(x, FIX2INT(base), Qtrue);
  +}

この部分を以下のように修正してください．

+VALUE
+rb_big2str_karatsuba(VALUE x, int base)
+{

• return rb_big2str0_karatsuba(x, base, Qtrue);
  +}

あと、Karatsubaといえばかけ算
の高速化についても(アルゴリズムが理解できず)ほったらかしだっ
たんですよねえ。

今すぐというわけにはいかないのですが，こちらも手をつけようと思っています．
Ruby にはできるだけ速くなってもらいたいです

[Kenta_M]

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

In message “Re: [ruby-dev:31327] Re: Bignum#to_s e$B$Ne(B Karatsuba
e$B4p?tJQ49$K$h$k9bB.2=e(B”
on Wed, 1 Aug 2007 18:37:16 +0900, “Kenta M.”
[email protected] writes:

|e$BF1$8>r7o$G=hM};~4V$r7WB,$7$F!$C;$$J}$r:NMQ$7$?$i$$$$$H;W$$$^$7$?!%e(B
|e$B$=$3$G!$E:IU$N$h$&$J%Q%C%A$H!$%Y%s%A%^!<%/%W%m%0%i%$G7WB,$7$?$H$3$me(B |e$B0J2<$N$h$&$K$J$j$^$7$?!%e(B | |$ ./ruby -I lib karatsuba.rb |Rehearsal -------------------------------------------------- |original 2.410000 0.000000 2.410000 ( 9.625259) |ruby-dev:31312 2.420000 0.000000 2.420000 ( 9.635740) |ruby-dev:31323 1.740000 0.000000 1.740000 ( 6.842046) |----------------------------------------- total: 6.570000sec | | user system total real |original 2.420000 0.000000 2.420000 ( 9.931306) |ruby-dev:31312 2.420000 0.000000 2.420000 ( 9.627448) |ruby-dev:31323 1.740000 0.000000 1.740000 ( 6.842890) | |e$B$J$<$+e(B ruby-dev:31312 e$B$,!$%*%j%8%J%k$HHf3S$7$FAa$/$J$C$F$J$$$N$G$9$,!$e(B |e$B%Y%s%A%^!<%/%W%m%0%i%$,0-$$$N$G$7$g$&$+!&!&!&e(B
|e$BC1=c$Ke(B[ruby-dev:31312] e$B$,B.$/$J$k>r7o$H!$;d$Ne(B [ruby-dev:31323] e$B$,e(B
|e$BB.$/$J$k>r7o$,0c$&$H$$$&M}2r$GNI$$$b$N$+$I$&$+!%e(B

e$B1sF#$5$s$K$bH?7b$N5!2q$,$"$C$?J}$,$h$$$G$7$g$&$M!#$b$&$A$g$Ce(B
e$B$HBT$C$F$+$i<h$j9~$_$^$9!#e(B

|> e$B$"$H!“e(BKaratsubae$B$H$$$($P$+$1;;e(B
|> e$B$N9bB.2=$K$D$$$F$be(B(e$B%”%k%4%j%:%`$,M}2r$G$-$:e(B)e$B$[$C$?$i$+$7$@$Ce(B
|> e$B$?$s$G$9$h$M$(!#e(B
|
|e$B:#$9$0$H$$$&$o$1$K$O$$$+$J$$$N$G$9$,!$$3$A$i$b<j$r$D$1$h$&$H;W$C$F$$$^$9!%e(B
|Ruby e$B$K$O$G$-$k$@$1B.$/$J$C$F$b$i$$$?$$$G$9e(B

e$B$“$j$,$H$&$4$6$$$^$9!#;d<+?H$O%9%T!<%I%^%K%”$G$O$J$$$N$G!“$Ie(B
e$B$&$7$F$bB>$N8@8l$KNt$kItJ,$,=P$F$-$F$7$^$&$N$G$9$,!”$_$J$5$se(B
e$B$N$46(NO$N$*$+$2$G2~A1$5$l$F$-$F$$$^$9!#e(B

[Kenta_M]

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

e$B%a%s%F%J%s%9$G$-$k?M$,$$$k$J$i$I$C$A$G$b$$$$$G$9!#e(B

e$B;d$N%Q%C%A$O$J$k$Y$/=>Mh$N%W%m%0%i%`$K1F6A$rM?$($J$$$h$&$K5$$r$D$1$?e(B
e$B$D$b$j$G$9e(B (e$B$"$H!"$J$k$Y$/=$@5ItJ,$r8:$i$9e(B) e$B!#e(B

e$B0J2<!"$`$i$1$s$5$s$N%Q%C%A$rFI$^$:$Ke(B 2 e$BE@$@$1;XE&$7$^$9!#e(B

1. e$B;d$N%Q%C%A$O!"?t@i7e0J2<$Ne(B bignum
   e$B$KBP$7$F$O%*%j%8%J%k$N%k!<%A%s$re(B
   e$B;H$&$h$&$K$7$F$$$^$9!#$`$i$1$s$5$s$N%F%9%H%Y%s%A$G8z2L$,=P$J$$$N$Oe(B
   e$BB?J,$3$N$?$a$G$9!#==?t7e$G$b8z2L$,$"$k$3$H$,$"$k$s$G$9$M!#e(B

e$B$?$@ogCM$rBg$-$/$H$C$?$N$K$OM}M3$,$"$j$^$9!#e(BKaratsuba
e$B$N%"%k%4%j%:%`$Oe(B
e$BCfESH>C<$JD9$5$Ne(B bignum e$B$KBP$7$F!"5U$KCY$/$J$k$+$i$G$9!#e(B

e$B%*%j%8%J%kHGe(B

$ time ./ruby.org -e ‘1000000.times { 10000000000000.to_s }’

real 0m1.635s
user 0m0.120s
sys 0m1.520s

e$B$`$i$1$s$5$s%Q%C%AHGe(B

$ time ./ruby -e ‘1000000.times { 10000000000000.to_s }’

real 0m3.911s
user 0m0.560s
sys 0m3.360s

1 e$B2s$"$?$j$NB.EYNt2=$OHy!9$?$k$b$N$G$9$,!"e(B65536**65536
e$B$N$h$&$JD6$G$+$$e(B
bignum e$B$re(B to_s e$B$9$k>l9g$h$j!"e(B10000000000000
e$BDxEY$N?t;z$re(B to_s e$B$9$k$3$H$Ne(B
e$BJ}$,D>46E*$K$OB?$=$&$G$9!#e(B
e$B$I$N$/$i$$$N?t;z$G5UE>$9$k$N$+$Oe(B (e$BLLE]$@$C$?$N$Ge(B)
e$BD4$Y$F$^$;$s!#e(B

2. e$B;d$N%Q%C%A$Oe(B to_s
   e$B$,=i$a$F8F$P$l$k$^$G%F!<%V%k$r=i4|2=$7$^$;$s!#e(B
   e$B$J$N$G0l2sL$Ne(B to_s e$B$OCY$/$J$j$^$9!#e(B

e$B1sF#%Q%C%AHGe(B

$ ./ruby -e ‘(x = 65536**65536).to_s; t = Time.new; x.to_s; p(Time.now -
t)’
8.390915

e$B$`$i$1$s$5$s%Q%C%AHGe(B

$ ./ruby -e ‘(x = 65536**65536).to_s; t = Time.new; x.to_s; p(Time.now -
t)’
10.460523

e$B$b$&$A$g$C$H@53N$K$O!"e(Bto_s(N)
e$B$,8F$P$l$F=i$a$F!"I,MW$J$H$3$m$@$1!“e(B
e$B4p?te(B N e$B$N%F!<%V%k$r=i4|2=$9$k46$8$G$9e(B
(e$BMW$9$k$K$”$^$j$G$+$/$J$$e(B
bignum e$B$Ne(B to_s e$B$KLBOG$r$+$1$k$3$H$O$J$$$D$b$je(B) e$B!#e(B

e$B$G$9$,!"$`$i$1$s$5$s$N%Q%C%A$O$Q$C$H8+%F!<%V%k$r;H$C$F$J$$!)e(B

e$B2~A1$NM>CO$,$"$k$N$+$b!#e(B

[Kenta_M]

e$B$`$i$1$s$G$9!%e(B

On 8/1/07, Yusuke ENDOH [email protected] wrote:

1. e$B;d$N%Q%C%A$O!“?t@i7e0J2<$Ne(B bignum e$B$KBP$7$F$O%*%j%8%J%k$N%k!<%A%s$re(B
   e$B;H$&$h$&$K$7$F$$$^$9!#$`$i$1$s$5$s$N%F%9%H%Y%s%A$G8z2L$,=P$J$$$N$Oe(B
   e$BB?J,$3$N$?$a$G$9!#==?t7e$G$b8z2L$,$”$k$3$H$,$"$k$s$G$9$M!#e(B

e$B$?$@ogCM$rBg$-$/$H$C$?$N$K$OM}M3$,$“$j$^$9!#e(BKaratsuba e$B$N%”%k%4%j%:%`$Oe(B
e$BCfESH>C<$JD9$5$Ne(B bignum e$B$KBP$7$F!"5U$KCY$/$J$k$+$i$G$9!#e(B

e$B$=$&$J$s$G$9$M!%%“%k%4%j%:%$N@-<A$K$O>\$7$/$J$+$C$?$N$GJY6/$K$J$j$^$9!%e(B e$B;d$b;n$7$F$_$^$7$?$,!$==?t7e$Ne(B Bignum e$B$KBP$7$F$O%*%j%8%J%k$Ne(B e$B%"%k%4%j%:%$NJ}$,B.$$$h$&$G$9$M!%$3$l$O!$$”$k7e?te(B N
e$B$KBP$7$F!$@5?te(B M e$B$,e(B
e$BB8:_$7$F$$$F!$e(BN < M e$B$N$H$-$KAGD>$K4p?t$G3d$j;;$7$F$$$/J}$,e(B
bigdivmod e$B$re(B
e$B7+$jJV$9$h$jB.$$$H$$$&$3$H$J$s$G$7$g$&$+$M!)e(B

e$B$b$&$A$g$C$H@53N$K$O!"e(Bto_s(N) e$B$,8F$P$l$F=i$a$F!"I,MW$J$H$3$m$@$1!“e(B
e$B4p?te(B N e$B$N%F!<%V%k$r=i4|2=$9$k46$8$G$9e(B (e$BMW$9$k$K$”$^$j$G$+$/$J$$e(B
bignum e$B$Ne(B to_s e$B$KLBOG$r$+$1$k$3$H$O$J$$$D$b$je(B) e$B!#e(B

e$B$G$9$,!"$`$i$1$s$5$s$N%Q%C%A$O$Q$C$H8+%F!<%V%k$r;H$C$F$J$$!)e(B

e$B2~A1$NM>CO$,$"$k$N$+$b!#e(B

e$B0l1~!$%F!<%V%k$C$]$$$3$H$O$d$C$F$$$^$9$,!$$=$NItJ,$,8zN($h$/L5$$$H$O<+J,$Ge(B
e$B$b;W$C$F$$$^$7$?!%$=$7$F!$1sF#$5$s$NJQ99ItJ,$r??7u$KFI$^$;$F$$$?$@$-$^$7$F!$e(B
e$B%O%C%7%e$J$s$F;H$&I,MW$J$/$F!$AGD>$KG[Ns$G4IM}$G$-$k;v$K5$$E$-$^$7$?!%e(B
e$B$b$&0l$D!$;d$N<BAu$,AGD>$K:F5"$r;H$C$F<BAu$7$F$$$k$H$3$m$r!$e(B
e$B1sF#$5$s$N<BAu$O%k!<%W$KJQ49$5$l$$$^$9$M!%$I$&8+$F$b1sF#$5$s$N<BAu$N$[$&$,e(B
e$BJ?6Q$9$k$H9bB.$G$“$k$h$&$K8+$($^$9!%;d$N<BAu$O!$4p?t%Y%-$N%-%c%C%7%e%(%s%H%je(B
e$B?t$,1sF#$5$s$N<BAu$Ne(B2e$BG$”$k$N$G!$Bg$-$J7e?t$NJQ49$r2?EY$b$d$k$H$-$KM-Mxe(B
e$B$K$J$C$?$N$@$m$&$H;W$$$^$9!%e(B

e$B$H$$$&$3$H$G!$%Q%C%A$O1sF#$5$s$N%P!<%8%g%s$r:NMQ$7$F$$$?$@$/J}8~$G$h$$$H;W$$$^$9!%e(B

[Kenta_M]

むらたです．

On 8/1/07, Yusuke ENDOH [email protected] wrote:

ただ閾値を大きくとったのには理由があります。Karatsuba のアルゴリズムは
中途半端な長さの bignum に対して、逆に遅くなるからです。
(snip)
1 回あたりの速度劣化は微々たるものですが、65536**65536 のような超でかい
bignum ã‚’ to_s ã™ã‚‹å ´åˆã‚ˆã‚Šã€10000000000000 程度の数字を to_s することの
方が直感的には多そうです。
どのくらいの数字で逆転するのかは (面倒だったので) 調べてません。

KARATSUBA_DIGITS を 1024, 512, 256, 128 と変化させて処理時間を計測しました．

$ ./ruby_1024 -e ‘(x = 6553665536).to_s; s=Time.now; x.to_s;
puts(Time.now-s)’
23.048639
$ ./ruby_512 -e '(x = 6553665536).to_s; s=Time.now; x.to_s;
puts(Time.now-s)’
11.716184
$ ./ruby_256 -e ‘(x = 6553665536).to_s; s=Time.now; x.to_s;
puts(Time.now-s)’
11.425493
$ ./ruby_128 -e '(x = 6553665536).to_s; s=Time.now; x.to_s;
puts(Time.now-s)’
23.960106

以上の結果から，256桁と128桁の間で逆転していることが分かります．
そこで提案ですが，KARATSUBA_DIGITS を 256 にして，big2str_table の
エントリ数を 16 から 64 に増やすというのはどうでしょう？

[ruby-dev:31312] ã§é è—¤ã•ã‚“ãŒè¡Œã£ãŸå¤‰æ›´ã‚‚å«ã‚€æ–°ã—ã„ãƒ‘ãƒƒãƒã‚’æ·»ä»˜ã—ã¾ã—ãŸï¼Ž
テーブルのエントリ数のために MAX_BIG2STR_TABLE_ENTRIES を定義しました．

[Kenta_M]

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

e$B$"$H!“e(BKaratsubae$B$H$$$($P$+$1;;e(B
e$B$N9bB.2=$K$D$$$F$be(B(e$B%”%k%4%j%:%`$,M}2r$G$-$:e(B)e$B$[$C$?$i$+$7$@$Ce(B
e$B$?$s$G$9$h$M$(!#e(B

e$B$F$C$-$je(B ruby-list:35759
e$B$,:NMQ$5$l$F$$$k$b$N$@$H;W$C$F$$$^$7$?!#e(B
e$BEv3:%5%$%H$O$b$&>C$($F$7$^$C$F$$$k$h$&$J$N$G$9$,!"C/$+$N<j85$Ke(B
e$B%3!<%I$,;D$C$F$$$J$$$N$G$7$g$&$+!#e(B

[Kenta_M]

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

e$B$?$@ogCM$rBg$-$/$H$C$?$N$K$OM}M3$,$"$j$^$9!#e(BKaratsuba e$B$N%"%k%4%j%:%`$Oe(B
e$BCfESH>C<$JD9$5$Ne(B bignum e$B$KBP$7$F!"5U$KCY$/$J$k$+$i$G$9!#e(B

e$B$=$&$J$s$G$9$M!%%"%k%4%j%:%`$N@-<A$K$O>$7$/$J$+$C$?$N$GJY6/$K$J$j$^$9!%e(B

e$B;d$bJL$K>$7$$$o$1$8$c$J$$$G$9e(B (e$B>Pe(B)

e$B$I$&8+$F$b1sF#$5$s$N<BAu$N$[$&$,J?6Q$9$k$H9bB.$G$"$k$h$&$K8+$($^$9!%e(B

e$B$$$(!"J?6Q$9$k$H$`$i$?$5$s$NJ}$,Aa$$$G$9!#e(B

$ ruby -e ‘100.times { puts “puts((#{ rand(50000) }**#{
rand(50000)}).to_s(#{ rand(35) + 2 }))” }’ > test_bignum.rb
$ time ./ruby.endoh test_bignum.rb > res.endoh.txt
real 2m53.565s
user 0m10.850s
sys 2m41.210s
$ time ./ruby.murata test_bignum.rb > res.murata.txt
real 2m32.398s
user 0m10.960s
sys 2m20.640s

e$BFC$K0l2sL$Ne(B to_s
e$B$,Cx$7$/CY$$$N$G!"2?$+2<<j$r$7$F$$$k5$$,$7$^$9!#e(B

$ ./ruby.endoh -e ‘t=Time.now; 3.times { (6553665536).to_s;
t2=Time.now; p(t2-t); t=t2 }’
12.353483
8.567412
8.499522
$ ./ruby.murata -e 't=Time.now; 3.times { (6553665536).to_s;
t2=Time.now; p(t2-t); t=t2 }’
8.295727
7.553404
9.150195

e$B<XB-$G$9$,!"$`$i$?$5$sHG$@$He(B to_s(2)
e$B$K<:GT$9$k$3$H$,$"$k$_$?$$$G$9!#e(B

$ ./ruby.murata -e ‘(6553665536).to_s(2)’
-e:1: warning: in ab, b may be too big
-e:1: warning: Bignum out of Float range
-e:1:in `to_s’: wrong number of arguments (1 for 0) (ArgumentError)
from -e:1

KARATSUBA_DIGITS e$B$re(B 1024, 512, 256, 128 e$B$HJQ2=$5$;$F=hM};~4V$r7WB,$7$^$7$?!%e(B
(e$BN,e(B)
e$B0J>e$N7k2L$+$i!$e(B256e$B7e$He(B128e$B7e$N4V$G5UE>$7$F$$$k$3$H$,J,$+$j$^$9!%e(B
e$B$=$3$GDs0F$G$9$,!$e(BKARATSUBA_DIGITS e$B$re(B 256 e$B$K$7$F!$e(Bbig2str_table e$B$Ne(B
e$B%(%s%H%j?t$re(B 16 e$B$+$ie(B 64 e$B$KA}$d$9$H$$$&$N$O$I$&$G$7$g$&!)e(B

e$B$J$k$[$I!"$h$5$=$&$G$9!#e(B
1.8 e$BMQ$K0?"$b$7$F$/$@$5$C$F$"$j$,$H$&$4$6$$$^$9!#e(B

[Kenta_M]

e$B$`$i$1$s$G$9!%e(B

On 8/3/07, Yusuke ENDOH [email protected] wrote:

e$B$"$H!“e(BKaratsubae$B$H$$$($P$+$1;;e(B
e$B$N9bB.2=$K$D$$$F$be(B(e$B%”%k%4%j%:%`$,M}2r$G$-$:e(B)e$B$[$C$?$i$+$7$@$Ce(B
e$B$?$s$G$9$h$M$(!#e(B

e$B$F$C$-$je(B ruby-list:35759 e$B$,:NMQ$5$l$F$$$k$b$N$@$H;W$C$F$$$^$7$?!#e(B
e$BEv3:%5%$%H$O$b$&>C$($F$7$^$C$F$$$k$h$&$J$N$G$9$,!"C/$+$N<j85$Ke(B
e$B%3!<%I$,;D$C$F$$$J$$$N$G$7$g$&$+!#e(B

ruby-list:35759 e$B$O!$e(BGoogle e$B$G8!:w$7$F$$?$H$3$m!$e(B
e$B$^$C$I$5$$$($s$F$#$9$H$NCS>e$5$s$$?$$$G$9!%e(B

OSC Hokkaido e$B$G$Ne(B Haskell e$B$N9V1i$OLLGr$+$C$?$G$9!%e(B

http://madscientist.jp/~ikegami/ruby/
e$B9`L$O$"$j$^$9$,!$%3%s%F%s%D$OB8:_$7$J$$$h$&$G$9!%e(B

[Kenta_M]

e$B$`$i$?$G$9!%e(B

07/08/02 e$B$Ke(B Yusuke ENDOH[email protected] e$B$5$s$O=q$-$^$7$?e(B:

$ time ./ruby.murata test_bignum.rb > res.murata.txt
real 2m32.398s
user 0m10.960s
sys 2m20.640s

e$B$"$l$'e(B (e$B4@e(B) e$B;d$NJ}$,B.$$!)!)$A$g$C$HIT;W5D$G$9$M!&!&!&e(B
e$BC1=c$K%F!<%V%k$N%(%s%H%j?t$,;d$N<BAu$G$Oe(B 32
e$B$G1sF#$5$s$N<BAu$G$Oe(B 16
e$B$K$J$C$F$$$^$9$,!$%F!<%V%k$N;H$$J}$,0c$&$N$GC1=c$K$3$l$,B.EY:9$Ke(B
e$B$J$C$F$$$k$H$b;W$($J$$$7!&!&!&e(B

e$B0x$_$K!$;d$N<BAu$N%F!<%V%k$N;H$$J}$O:#9M$($k$H!$8zN(0-$$$N$Ge(B
e$B$b$7;d$N$[$&$,:NMQ$5$l$k$N$G$7$?$i!$%F!<%V%k<~JU$r2~NI$7$^$9!%e(B

7.553404
9.150195

e$B<XB-$G$9$,!“$`$i$?$5$sHG$@$He(B to_s(2) e$B$K<:GT$9$k$3$H$,$”$k$_$?$$$G$9!#e(B

$ ./ruby.murata -e ‘(6553665536).to_s(2)’
-e:1: warning: in ab, b may be too big
-e:1: warning: Bignum out of Float range
-e:1:in `to_s’: wrong number of arguments (1 for 0) (ArgumentError)
from -e:1

e$B$3$l$O!&!&!&:G=i$N7Y9p$O$-$C$H4p?t$N%Y%-$r5a$a$h$&$H$7$?$H$-$KH/@8$7$Fe(B
e$B$k$b$N$@$H;W$$$^$9e(B (e$B$=$3$7$+$J$$$G$9$7e(B)e$B!%e(B

e$B;d$,:rF|Ds=P$7$?%Q%C%A$H!$e(B[ruby-dev:31323]
e$B$G;d$,Ds=P$7$?%Q%C%A$Ne(B
e$BB.EY$r$^$@Hf3S$7$F$$$^$;$s$G$7$?!%$H$j$"$($:!$$=$NHf3S7k2L$r8e$[$Ie(B
e$BJs9p$7$?$$$H;W$$$^$9!%e(B

[Kenta_M]

At Fri, 3 Aug 2007 21:55:19 +0900,
Kenta M. wrote:

user 0m10.960s
sys 2m20.640s

e$B$"$l$'e(B (e$B4@e(B) e$B;d$NJ}$,B.$$!)!)$A$g$C$HIT;W5D$G$9$M!&!&!&e(B

CPU e$B$H$+%3%s%Q%$%i$H$+%3%s%Q%$%k;~%*%W%7%g%s$J$I$Oe(B
e$B$*FsJ}$GF1$8$J$s$G$7$g$&$+e(B? CPU e$B$K0M$C$F5UE>$9$ke(B
e$B$N$G$"$l$P!"N>J}:NMQ$7$F%3%s%Q%$%k;~$K@Z$jBX$($ke(B
e$B$h$&$K$9$k$H$+e(B?

e$B%3!<%I$OA4A3FI$s$G$J$$$N$G!"$=$l$i$K0MB8$7$J$$$Ne(B
e$B$G$7$?$i$9$_$^$;$se(B (e$BFI$s$G$b;d$K$O$o$+$i$J$$$+e(B :-X)e$B!#e(B

[Kenta_M]

むらたです．こんばんわ．

[ruby-dev:31323] で提出したパッチに対して，テーブル周辺の処理を変更した
改良版をこしらえました．一つ目の添付パッチがそれです．この変更で，
ã„ãã‚‰ã‹é«˜é€ŸåŒ–ã§ãã¾ã—ãŸã®ã§ï¼Œä»¥ä¸‹ã§å ±å‘Šã—ã¾ã™ï¼Ž

07/08/03 に Kenta M.[email protected] さんは書きました:

07/08/02 に Yusuke ENDOH[email protected] さんは書きました:

ã©ã†è¦‹ã¦ã‚‚é è—¤ã•ã‚“ã®å®Ÿè£…ã®ã»ã†ãŒå¹³å‡ã™ã‚‹ã¨é«˜é€Ÿã§ã‚ã‚‹ã‚ˆã†ã«è¦‹ãˆã¾ã™ï¼Ž

いえ、平均するとむらたさんの方が早いです。

ç§ã®å®Ÿè£…ãŒé è—¤ã•ã‚“ã®å®Ÿè£…ã‚ˆã‚Šã‚‚å¹³å‡ã—ã¦é€Ÿã‹ã£ãŸç†ç”±ãŒåˆ†ã‹ã‚Šã¾ã—ãŸï¼Ž
é è—¤ã•ã‚“ã®å®Ÿè£…ã«ãŠã„ã¦ï¼Œbig2str_karatsuba() 関数のはじめの方で
基数ベキを生成しているループがあります．その中で，必ず一回だけ，
余分な bigsqr が呼び出されてしまいます (結果は比較で使うだけ)．

ã‚‚ã†ä¸€ç‚¹ï¼Žé è—¤ã•ã‚“ã®å®Ÿè£…ã§ã¯ï¼Œå¤‰æ›å¯¾è±¡ã®æ•°å€¤ã‚’ï¼Œ2^n で2等分することを
繰り返して処理しています．僕の実装はというと，2等分ではなくて 2^n で
divmod した結果の値に応じて基数ベキの大きさを変えているので，
é™¤ç®—ã®çµæžœãŒæ€¥æ¿€ã«å°ã•ãªå€¤ã«ãªã£ãŸå ´åˆã«å†å¸°å‘¼ã³å‡ºã—ã®å›žæ•°ãŒå°‘ãªããªã‚Šã¾ã™ï¼Ž
この違いが，平均速度の差に現れているように思えます．

再帰よりもループの方が僅かながら軽いはずですから，従って，
to_s される値の内部表現によっては，僕の実装の方が遅くなることがある
かもしれません (ないかもしれません)．

特に一回目の to_s が著しく遅いので、何か下手をしている気がします。

é è—¤ã•ã‚“ã®å®Ÿè£…ã§åˆå›žã® to_s が著しく遅い理由は，今のところ発見できていません orz

蛇足ですが、むらたさん版だと to_s(2) に失敗することがあるみたいです。
(snip)
これは・・・最初の警告はきっと基数のベキを求めようとしたときに発生して
るものだと思います (そこしかないですし)．

その通りでした．基数が小さいと，rb_big_pow でベキを計算できなくなる
ã“ã¨ã‚’è€ƒãˆã¦ã„ã¾ã›ã‚“ã§ã—ãŸï¼Žæ–°ã—ã„ãƒ‘ãƒƒãƒã§ã¯ï¼Œé è—¤ã•ã‚“ã®å®Ÿè£…ã‚’å‚è€ƒã«ï¼Œ
小さなベキから bigsqr を使って計算するようにしたので，この問題は解決しています．

私が昨日提出したパッチと，[ruby-dev:31323] で私が提出したパッチの
速度をまだ比較していませんでした．とりあえず，その比較結果を後ほど
å ±å‘Šã—ãŸã„ã¨æ€ã„ã¾ã™ï¼Ž

で，このメールに添付したパッチと，[ruby-dev:31339] に添付したパッチの
速度を比較した結果を以下に示します．比較用に両方の変更をマージしたパッチを
２つ目のファイルとして添付しました．コンパイルオプションは
CFLAGS=‘-O6 -mtune=pentium4 -march=i686’ としています．
次のような簡単なテストで，私の新しい方が平均的に速いことが分かりました．

$ ruby -e ‘100.times { puts
“(#{rand(50000)}**#{rand(50000)}).to_s(#{rand(35) + 2})” }’ >
test_bignum_endoh.rb
$ sed -e ‘s/to_s/to_s2/g’ test_bignum_endoh.rb > test_bignum_muraken.rb
$ time ./ruby test_bignum_endoh.rb > res.endoh.txt

real 11m7.579s
user 3m45.882s
sys 0m0.036s
$ time ./ruby test_bignum_muraken.rb > res.muraken.txt

real 10m14.448s
user 3m23.973s
sys 0m0.028s

今回の改変作業中に，bigdivmod，bigsqr，もしくは rb_big_mul0 のいずれかの
バグ(?)を見つけました (まだ直してはいません)．
僕が確認した症状は，bigdivmod の引数 y ãŒæ­£è¦åŒ–ã•ã‚Œã¦ã„ãªã„å ´åˆã«ï¼Œ
商 q が不正な値になります．具体例を出すと，

x = [3326864467, 3907086170, 971956897, 690519217, 3899134773,
3795824570, 442283194, 1330259551, 2003237075, 185150596,
3356760681, 1324341631, 2994369366, 4193523868, 856144703,
901986172, 819949625, 3949855622, 1036270654, 861377302,
1540531469, 1872568982, 2117697280, 1626080396, 914652449,
2236519255, 1632014126, 2752481805, 1004969631, 2885238682,
746945629, 2700918791, 1532651932, 15071 ]

y = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 ]

となっている (y が正規化されていない) ときに商 q が不正な値になります．
剰余 r には影響はありませんでした．

一つ目の添付のパッチを当てたソースでこの症状が出る部分は，1101行目にある
bigdivmod(x, b, &q, &r) という呼び出しです．ここで，b が正規化されていない
ために症状が発生したわけですが，b は rb_big_pow か bigsqr のどちらかによって
生成されるオブジェクトです．両者のコードを見ると，bigsqr で呼び出している
rb_big_mul0 の中で作られる Bignum が bigtrunc もしくは bignorm されずに
æˆ»ã•ã‚Œã¦ã„ã‚‹ã®ã§ï¼Œã“ã‚ŒãŒåŽŸå› ã§ã¯ãªã„ã‹ã¨æ€ã„ã¾ã™ï¼Ž

もっとも，bigdivmod を非正規化オブジェクトでも正しく動くように修正することでも対応
出来ると思いますが，bigsqr の中で rb_big_mul0 を呼び出しているところに bigtrunc
を被せるだけで修正できるので，bigsqr をいじるほうが簡単だと思います
（もしくは rb_big_mul0 で z を bigtrunc する）．

どちらを行うべきかは Bignum のライブラリとしての仕様の問題だと思うので，
最終的にはまつもとさんの判断にお任せします．

[Kenta_M]

むらたです．

07/08/07 に Yukihiro M.[email protected] さんは書きました:

スになっているようですが、すでに前回のパッチが取り込まれてい
ますから、現在のtrunkとの差分を提出していただけませんか？

1.8.x のブランチで作業してました．

次の 1.8.x のリリースに混ざれればいいなぁと思いまして・・・

とりあえずbigdivmodを非正規化オブジェクトでも動くようにする意
図はないので、bigsqrの修正で対応するのがよいのではないでしょ
うか。こちらもパッチを作っていただけませんか？

bigsqr への修正も含めた現在の trunk に対する patch を添付しました．
どうぞ，お納めください．

ちなみに， [ruby-dev:31352] で使ったテストスクリプトと同じものを
trunk 版で実行して時間を計ってみると (CFLAGS は同じ)

$ time ./ruby …/ruby_1_8_bignum_to_s/test_bignum_endoh.rb > res
real 9m24.412s
user 3m24.145s
sys 0m0.048s

さらに1åˆ†ã»ã©é€Ÿããªã£ãŸã‚ã‘ã§ã™ãŒï¼Œåˆ¶å¾¡æ§‹é€ ãŒä½•ä¸€ã¤ç„¡ã„ã‚¹ã‚¯ãƒªãƒ—ãƒˆã§ã‚‚
YARV 効果が現れるんですね．初めて 1.9 を動かしましたが，驚きです．

[Kenta_M]

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

In message “Re: [ruby-dev:31352] Re: Bignum#to_s e$B$Ne(B Karatsuba
e$B4p?tJQ49$K$h$k9bB.2=e(B”
on Tue, 7 Aug 2007 00:50:27 +0900, “Kenta M.”
[email protected] writes:

|[ruby-dev:31323] e$B$GDs=P$7$?%Q%C%A$KBP$7$F!$%F!<%V%k<~JU$N=hM}$rJQ99$7$?e(B
|e$B2~NIHG$r$3$7$i$($^$7$?!%0l$DL$NE:IU%Q%C%A$,$=$l$G$9!%$3$NJQ99$G!$e(B
|e$B$$$/$i$+9bB.2=$G$-$^$7$?$N$G!$0J2<$GJs9p$7$^$9!%e(B

e$B$“$j$,$H$&$4$6$$$^$9!#%Q%C%A$O$I$&$d$i$A$g$C$H8E$$e(Btrunke$B$,%Y!<e(B
e$B%9$K$J$C$F$$$k$h$&$G$9$,!”$9$G$KA02s$N%Q%C%A$,<h$j9~$^$l$F$$e(B
e$B$^$9$+$i!"8=:_$Ne(Btrunke$B$H$N:9J,$rDs=P$7$F$$$?$@$1$^$;$s$+!)e(B

|e$B0l$DL$NE:IU$N%Q%C%A$rEv$F$?%=!<%9$G$3$N>I>u$,=P$kItJ,$O!$e(B1101e$B9TL$K$"$ke(B
|bigdivmod(x, b, &q, &r) e$B$H$$$&8F$S=P$7$G$9!%$3$3$G!$e(Bb e$B$,@55,2=$5$l$F$$$J$$e(B
|e$B$?$a$K>I>u$,H/@8$7$?$o$1$G$9$,!$e(Bb e$B$Oe(B rb_big_pow e$B$+e(B bigsqr e$B$N$I$A$i$+$K$h$C$Fe(B
|e$B@8@.$5$l$k%%V%8%'%/%H$G$9!%N><T$N%3!<%I$r8+$k$H!$e(Bbigsqr e$B$G8F$S=P$7$F$$$ke(B
|rb_big_mul0 e$B$NCf$G:n$i$l$ke(B Bignum e$B$,e(B bigtrunc e$B$b$7$/$Oe(B bignorm e$B$5$l$:$Ke(B
|e$BLa$5$l$F$$$k$N$G!$$3$l$,860x$G$O$J$$$+$H;W$$$^$9!%e(B
|
|e$B$b$C$H$b!$e(Bbigdivmod e$B$rHs@55,2=%%V%8%'%/%H$G$b@5$7$/F0$/$h$&$K=$@5$9$k$3$H$G$bBP1~e(B
|e$B=PMh$k$H;W$$$^$9$,!$e(Bbigsqr e$B$NCf$Ge(B rb_big_mul0 e$B$r8F$S=P$7$F$$$k$H$3$m$Ke(B bigtrunc
|e$B$rHo$;$k$@$1$G=$@5$G$-$k$N$G!$e(Bbigsqr e$B$r$$$8$k$[$&$,4JC1$@$H;W$$$^$9e(B
|e$B!J$b$7$/$Oe(B rb_big_mul0 e$B$Ge(B z e$B$re(B bigtrunc e$B$9$k!K!%e(B
|
|e$B$I$A$i$r9T$&$Y$-$+$Oe(B Bignum e$B$N%i%$%V%i%j$H$7$F$N;EMM$NLdBj$@$H;W$&$N$G!$e(B
|e$B:G=E$K$O$^$D$b$H$5$s$NH=CG$K$*G$$;$7$^$9!%e(B

e$B$H$j$"$($:e(Bbigdivmode$B$rHs@55,2=%*%V%8%'%/%H$G$bF0$/$h$&$K$9$k0Ue(B
e$B?^$O$J$$$N$G!"e(Bbigsqre$B$N=$@5$GBP1~$9$k$N$,$h$$$N$G$O$J$$$G$7$ge(B
e$B$&$+!#$3$A$i$b%Q%C%A$r:n$C$F$$$?$@$1$^$;$s$+!)e(B

[Kenta_M]

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

In message “Re: [ruby-dev:31354] Re: Bignum#to_s e$B$Ne(B Karatsuba
e$B4p?tJQ49$K$h$k9bB.2=e(B”
on Tue, 7 Aug 2007 02:11:41 +0900, “Kenta M.”
[email protected] writes:

|> e$B$“$j$,$H$&$4$6$$$^$9!#%Q%C%A$O$I$&$d$i$A$g$C$H8E$$e(Btrunke$B$,%Y!<e(B
|> e$B%9$K$J$C$F$$$k$h$&$G$9$,!”$9$G$KA02s$N%Q%C%A$,<h$j9~$^$l$F$$e(B
|> e$B$^$9$+$i!"8=:_$Ne(Btrunke$B$H$N:9J,$rDs=P$7$F$$$?$@$1$^$;$s$+!)e(B
|
|1.8.x e$B$N%V%i%s%A$G:n6H$7$F$^$7$?!%e(B
|
|# e$B<!$Ne(B 1.8.x e$B$N%j%j!<%9$K:.$6$l$l$P$$$$$J$!$H;W$$$^$7$F!&!&!&e(B

e$B$^$:$Oe(B1.9e$B$G:n6H$7$^$7$g$&!#e(B1.8e$B%j%j!<%9$KF~$l$k$+$I$&$+$Oe(Bknu
e$B$5$s$,7hDj$7$^$9!#e(Bknue$B$5$s$+$ie(BGOe$B$,=P$l$P$=$A$i$K%3%_%C%H$H$$e(B
e$B$&$3$H$G!#e(B

e$B$7$+$7!“:#8ee(B1.8e$B$He(B1.9e$B$H$NP*N%$,$h$jBg$-$/$J$C$?$i!”$=$l$G$O$&e(B
e$B$^$/$$$+$J$$$3$H$bB?$/$J$k$G$7$g$&$M!#$I$&$7$h$&!#e(B

|bigsqr e$B$X$N=$@5$b4^$a$?8=:_$Ne(B trunk e$B$KBP$9$ke(B patch e$B$rE:IU$7$^$7$?!%e(B
|e$B$I$&$>!$$*G<$a$/$@$5$$!%e(B

trunke$B$K<h$j9~$b$&$H;W$$$^$9!#e(B