多倍長整数演算の速度比較

rubyperlpython多倍長整数演算の速度を適当に比較してみました。フィボナッチ数の計算速度比較以上にどーでもいい比較です。

前置き

使用した処理系のバージョンはそれぞれ以下のとおりです。

perl多倍長整数を扱う方法が何個かあるようなので、標準装備らしい bigint と、別途 CPAN でインストールしないといけない Math::BitInt::GMP (GMP の binding) の 2 種類を試しました。python の psyco はなんか動かなくて面倒だったので試してません。この比較にはあまり影響しないような気がしてます。僕は PerlPython は素人なので、もっと速くて美しい書き方・やり方があったら教えてください。

実験 1: 5 の累乗の計算

5 の 30,000 乗、100,000 乗、300,000 乗、1,000,000 乗の計算にかかる時間を調べました。単位は秒。

30000 100000 300000 1000000
ruby 0.09 0.13 0.78 8.21
python 0.14 0.12 0.31 1.37
perl(bigint) 3.67 37.05 N/A N/A
perl(GMP) 0.06 0.06 0.09 0.21

GMP は当然として python も結構速いです。python は乗算に Karatsuba 法を実装しているようです。perl の bigint は圧倒的に遅いです。100 秒超えたら N/A です。
以下ソース。n を数字に置き換えてください。

# ruby
5**n
# python
5**n
# perl (bigint)
use bigint;
5**n;
# perl (GMP)
use Math::BigInt lib => "GMP";
Math::BigInt->new(5)->bpow(n);

実験 2: 5 の累乗の表示

実験 1 の数字を 10 進表示するのにかかる時間を調べました。多倍長整数を文字列化するということは基数変換するということであり、これが結構時間のかかる処理なのです。

30000 100000 300000 1000000
ruby 0.01 0.05 4.05 42.88
python 0.24 3.16 28.92 N/A
perl(bigint) 0.01 1.74 N/A N/A
perl(GMP) 0.02 0.06 0.21 1.20

やはり GMP が圧倒的ですが、Ruby もかろうじて動きます。Ruby は基数変換に Karatsuba 法を用いているためです (ruby-dev:31323) 。ちょっと手前味噌
以下ソース。上の表の数値は下のソースの実行時間から実験 1 の数値を引いてあります (つまり累乗の計算時間は含みません) 。

# ruby
p(5**n)
# python
print(5**n)
# perl (bigint)
use bigint;
print(5**n);
print "\n";
# perl (GMP)
use Math::BigInt lib => "GMP";
print Math::BigInt->new(5)->bpow(n);
print "\n";

実験 3: 円周率の計算

最後に、多倍長整数を使って円周率を 100 桁、1,000 桁、10,000 桁計算する時間を調べました。

100 1000 10000
ruby 0.03 0.25 5.77
python 0.09 0.13 6.11
perl(bigint) 0.25 3.44 N/A
perl(GMP) 0.11 0.59 6.56

あれほど圧倒的だった GMP がなぜか普通です。もっと大きな桁で威力を発揮するのかな。rubypython はほぼ同じ。bigint はやっぱり全然ダメです。
以下ソース。python わからないのでなんだかかっこわるい。GMP の演算は破壊的なので copy() とか必要でうっとうしすぎます。

# ruby
a = b = 10 ** n
(n * 8 + 1).step(3, -2) do |i|
  a = (i / 2) * (a + b * 2) / i
end
puts "3.#{ a - b }"
# python
a = b = 10 ** n
for i in range(n * 8 + 1, 1, -2):
  a = divmod(divmod(i, 2)[0] * (a + b * 2), i)[0]
print("3." + str(a - b))
# perl (bigint)
use strict;
use bigint;

my $a;
my $b;
my $i;

$a = $b = 10 ** n;
for($i = n * 8 + 1; $i >= 3; $i -= 2) {
  $a = int(int($i / 2) * ($a + $b * 2) / $i);
}
$a -= $b;
print("3.$a\n");
# perl (GMP)
use strict;
use Math::BigInt lib => "GMP";

my $a = Math::BigInt->new(10)->bpow(n);
my $b = $a->copy();
my $i;
my $t;

for($i = n * 8 + 1; $i >= 3; $i -= 2) {
  $t = $b->copy();
  $a->badd($t);
  $a->badd($t);
  $t = Math::BigInt->new(int($i / 2));
  $t->bmul($a);
  $t->bdiv($i);
  $a = $t;
}
$a->bsub($b);
print("3.$a\n");

いい加減なまとめ

現状では、気軽に多倍長演算を享受したい時は rubypython がおすすめです。perl の bigint は速度がどうでもいいときだけ使いましょう速度が重要なら GMP とあわせて使いましょう。ソースを書くのが面倒でもそれなりに速く多倍長演算したいときは GMP がよさそうです。
以下追記:

H.I. 2008/01/17 10:09
「use bigint lib => 'GMP'」と書くことができて、GMP
operator/constant overload をしてくれるみたいです。

との情報をいただきました。Perl では記述性と速度を両取りする選択肢もあるようです。Perl はさすがですね。円周率 10000 桁で試したところ、10 秒でした。GMP を直接たたくより若干遅い *1 ようですが、記述性があがる方がいいですね。
あと、すべて実時間で計測してます。プロセスの初期化時間やコンパイル時間が含まれますので、0.0x のような小さい数値はあてにしないでください。

Appendix

以上の実験を自動でやってくれるスクリプトです。清書してないので読みにくくてごめんなさい。

require "timeout"

RB="./ruby19/local/bin/ruby"
PY="./python30/local/bin/python"
PL="./perl5/local/bin/perl"
LIMIT = 100

puts `#{RB} -v`
puts `#{PY} --version`
puts `#{PL} -v`.split("\n")[1]
puts

def test(prog, src, offset = 0)
  open("test-code", "w") {|fh| fh.print src }
  pid = fork
  unless pid
    $stdout.reopen(open("/dev/null", "w"))
    Process.setrlimit(Process::RLIMIT_CPU, LIMIT + 10)
    exec(prog, "test-code")
  end
  t = Time.now
  Process.wait
  t = Time.now - t
  puts(t > LIMIT ? "n/a" : "%3.3f" % (t - offset))
  t
end

def test_rb(src, offset = 0)
  print "ruby: "
  test(RB, src, offset)
end

def test_py(src, offset = 0)
  print "python: "
  test(PY, src, offset)
end

def test_pl(src, offset = 0)
  print "perl(bigint): "
  test(PL, src, offset)
end

def test_plg(src, offset = 0)
  print "perl(Math::BigInt::GMP): "
  test(PL, src, offset)
end

[30000, 100000, 300000, 1000000].each do |n|
  puts "5^#{n}"
  trb = test_rb "(5**#{n})"
  tpy = test_py "(5**#{n})"
  tpl = test_pl <<SRC
use strict;
use bigint;
5**#{n};
SRC
  tplg = test_plg <<SRC
use strict;
use Math::BigInt lib => "GMP";

Math::BigInt->new(5)->bpow(#{n});
SRC
  puts

  puts "5^#{n} with print"
  test_rb "p(5**#{n})", trb
  test_py "print(5**#{n})", tpy
  test_pl <<SRC, tpl
use strict;
use bigint;

print 5**#{n};
print "\\n";
SRC
  test_plg <<SRC, tplg
use strict;
use Math::BigInt lib => "GMP";

print Math::BigInt->new(5)->bpow(#{n});
print "\\n";
SRC
  puts
end

[100, 1000, 10000].each do |n|
  puts "#{n} digits of pi"
  test_rb <<SRC
a = b = 10 ** #{n}
#{n * 8 + 1}.step(3, -2) do |i|
  a = (i / 2) * (a + b * 2) / i
end
puts "3.\#{ a - b }"
SRC
  test_py <<SRC
a = b = 10 ** #{n}
for i in range(#{n * 8 + 1}, 1, -2):
  a = divmod(divmod(i, 2)[0] * (a + b * 2), i)[0]
print("3." + str(a - b))
SRC
  test_pl <<SRC
use strict;
use bigint;

my $a;
my $b;
my $i;

$a = $b = 10 ** #{n};
for($i = #{n * 8 + 1}; $i >= 3; $i -= 2) {
  $a = int(int($i / 2) * ($a + $b * 2) / $i);
}
$a -= $b;
print("3.$a\n");
SRC
  test_plg <<SRC
use strict;
use Math::BigInt lib => "GMP";

my $a = Math::BigInt->new(10)->bpow(#{n});
my $b = $a->copy();
my $i;
my $t;

for($i = #{n * 8 + 1}; $i >= 3; $i -= 2) {
  $t = $b->copy();
  $a->badd($t);
  $a->badd($t);
  $t = Math::BigInt->new(int($i / 2));
  $t->bmul($a);
  $t->bdiv($i);
  $a = $t;
}
$a->bsub($b);
print("3.$a\n");
SRC
  puts
end

*1:全然調べてませんが、Perl のオブジェクトと GMP のオブジェクトを毎回変換してるとかかな?