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

遠藤です。

メンテナンスできる人がいるならどっちでもいいです。

私のパッチはなるべく従来のプログラムに影響を与えないように気をつけた
つもりです (あと、なるべく修正部分を減らす) 。

以下、むらけんさんのパッチを読まずに 2 点だけ指摘します。


1. 私のパッチは、数千桁以下の bignum に対してはオリジナルのルーチンを
使うようにしています。むらけんさんのテストベンチで効果が出ないのは
多分このためです。十数桁でも効果があることがあるんですね。

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

# オリジナル版
$ time ./ruby.org -e '1000000.times { 10000000000000.to_s }'

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

# むらけんさんパッチ版
$ time ./ruby -e '1000000.times { 10000000000000.to_s }'

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

1 回あたりの速度劣化は微々たるものですが、65536**65536 のような超でかい
bignum を to_s する場合より、10000000000000 程度の数字を to_s することの
方が直感的には多そうです。
どのくらいの数字で逆転するのかは (面倒だったので) 調べてません。


2. 私のパッチは to_s が初めて呼ばれるまでテーブルを初期化しません。
なので一回目の to_s は遅くなります。

# 遠藤パッチ版
$ ./ruby -e '(x = 65536**65536).to_s; t = Time.new; x.to_s; p(Time.now - t)'
8.390915

# むらけんさんパッチ版
$ ./ruby -e '(x = 65536**65536).to_s; t = Time.new; x.to_s; p(Time.now - t)'
10.460523

もうちょっと正確には、to_s(N) が呼ばれて初めて、必要なところだけ、
基数 N のテーブルを初期化する感じです (要するにあまりでかくない
bignum の to_s に迷惑をかけることはないつもり) 。

# ですが、むらけんさんのパッチはぱっと見テーブルを使ってない？
# 改善の余地があるのかも。

-- 
Yusuke ENDOH <[e-mail]>