From: Yusuke ENDOH Date: 2007-08-01T20:23:20+09:00 Subject: [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