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

むらたです．

07/08/02 に Yusuke ENDOH<[e-mail]> さんは書きました:
> > どう見ても遠藤さんの実装のほうが平均すると高速であるように見えます．
>
> いえ、平均するとむらたさんの方が早いです。
>
> $ 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

あれぇ (汗) 私の方が速い？？ちょっと不思議ですね・・・
単純にテーブルのエントリ数が私の実装では 32 で遠藤さんの実装では 16
になっていますが，テーブルの使い方が違うので単純にこれが速度差に
なっているとも思えないし・・・

因みに，私の実装のテーブルの使い方は今考えると，効率悪いので
もし私のほうが採用されるのでしたら，テーブル周辺を改良します．

> 特に一回目の 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

これは・・・最初の警告はきっと基数のベキを求めようとしたときに発生して
るものだと思います (そこしかないですし)．

私が昨日提出したパッチと，[ruby-dev:31323] で私が提出したパッチの
速度をまだ比較していませんでした．とりあえず，その比較結果を後ほど
報告したいと思います．

--
Kenta Murata
OpenPGP FP = FA26 35D7 4F98 3498 0810 E0D5 F213 966F E9EB 0BCC