[ruby-dev:31340] Re: Bignum#to_s の Karatsuba 基数変換による高速化

遠藤です。

> > ただ閾値を大きくとったのには理由があります。Karatsuba のアルゴリズムは
> > 中途半端な長さの bignum に対して、逆に遅くなるからです。
>
> そうなんですね．アルゴリズムの性質には詳しくなかったので勉強になります．

私も別に詳しいわけじゃないです (笑)


> どう見ても遠藤さんの実装のほうが平均すると高速であるように見えます．

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

$ 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


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

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


蛇足ですが、むらたさん版だと to_s(2) に失敗することがあるみたいです。

$ ./ruby.murata -e '(65536**65536).to_s(2)'
-e:1: warning: in a**b, 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 を 1024, 512, 256, 128 と変化させて処理時間を計測しました．
(略)
> 以上の結果から，256桁と128桁の間で逆転していることが分かります．
> そこで提案ですが，KARATSUBA_DIGITS を 256 にして，big2str_table の
> エントリ数を 16 から 64 に増やすというのはどうでしょう？

なるほど、よさそうです。
1.8 用に移植もしてくださってありがとうございます。

-- 
Yusuke ENDOH <[e-mail]>