Bignum#* を Karatsuba 乗算で高速化した

Ruby

例によってどーでもいい速度の話ですが、Ruby の Bignum の乗算を Karatsuba 法で高速化しました (ruby-dev:37392) 。これで Python より一歩進んだ気がします。

今年の初めに書いた多倍長整数演算の速度比較の実験をやり直してみました。詳細はそっちをみてね。使用した処理系のバージョンはそれぞれ以下のとおり。

実験 1: 5 の累乗の計算

5 の 30,000 乗、100,000 乗、300,000 乗、1,000,000 乗の計算にかかる時間。単位は秒。

30000 100000 300000 1000000
ruby 0.02 0.08 0.37 1.69
python 0.04 0.11 0.32 1.76
perl(bigint) 4.88 44.19 N/A N/A
perl(GMP) 0.06 0.05 0.04 0.23

実験 2: 5 の累乗の表示

実験 1 の数字を 10 進表示するのにかかる時間。

30000 100000 300000 1000000
ruby 0.09 0.05 4.05 42.88
python 0.38 3.16 28.92 N/A
perl(bigint) 0.73 4.24 N/A N/A
perl(GMP) 0.02 0.02 0.02 0.80

実験 3: 円周率の計算

円周率を 100 桁、1,000 桁、10,000 桁計算する時間。

100 1000 10000
ruby 0.01 0.13 4.09
python 0.03 0.07 6.78
perl(bigint) 0.23 3.81 N/A
perl(GMP) 0.10 0.65 8.68

やっぱりいい加減なまとめ

気軽に多倍長演算したいときは Ruby がおすすめ、になったかなあ。ただしかなり適当に実験したので (1 回ずつ走らせただけ) 、変なとことかあるかも。
この先、考えられる最適化や実装ネタは、

  • Karatsuba 乗算に切り替える閾値を実験する (今は適当に決めうちしただけ)
  • FFT とかの乗算
  • ニュートン法による除算
  • pow_mod 、mod_inv 、probable_prime? (菊さんが実装しろとうるさい)

なんだけど、どれも本気でやるなら「GMP とか使えよ」という感じなので、なかなかやる気しない。ニュートン法なんかは面白そうなので誰かやらないかな。