Javaで階乗を高速に求めるメソッドを作る

階乗を求めるアルゴリズムというと、再帰関数を用いたものが広く知られています。

static long factorial (int i) {
	if (i==1) {return 1;}
	else {return i*factorial(i-1);}
}

for文を用いても同様の計算ができますが、これらの 1*2*3*4......N と順番に乗算していく方法では、
N！の N が非常に大きい数字になると高速に動作しなくなります。

そこで、N が大きい数字の場合でも高速に動作するようなプログラムを書いてみたいと思います。
N が大きいことが前提なので、扱う数値は BigInteger型 にしています。

ソースコード

static BigInteger bigFactorial (int n) {
	BigInteger[] ar = new BigInteger[n];
	for (int i=0; i<n; i++) {
		ar[i] = BigInteger.valueOf(i+1);
	}
	int t = 1, length = ar.length;
	while (t <= length) {
		for (int i=0; i<length; i+=(t<<1)) {
			if (t+i < length) {
				ar[i] = ar[i].multiply(ar[i+t]);
			}
		}
		t = t<<1;
	}
	return ar[0];
}

int型整数n を引数として与えると、n の階乗が BigInteger型 で返ってくるメソッドです。

どんな処理をしているかについては、言葉より図で説明したほうが手っ取り早いので、画像を貼ります。

上記の再帰関数では計算量が O(n) ですが、このように書くことで計算量を O(log n) に減らすことができます。
詳しくはわかりませんが、分割統治法というやり方と関係があるみたいです。

さて、このメソッド、速度は間違いなく速いのですが、最初に長さnの BigInteger型 の配列を用意する必要があるため、メモリ使用量が尋常ではありません。
最後に、気になる実行速度とメモリ使用量を計測してみましょう。

計測は、n=10 ～ n=100000 までの階乗をそれぞれ10回ずつ計算し、実行速度とメモリ使用量の平均を出すというやり方でおこないたいと思います。

計測に移る前に、今回作ったメソッドと比較する通常の階乗計算メソッドを紹介しておきます。

static BigInteger factorial (int n) {
	BigInteger bi = new BigInteger("1");
	for (int j=1; j<=n; j++) {
		bi = bi.multiply(BigInteger.valueOf(j));
	}
	return bi;
}

計測結果（実行速度）

	通常	高速
n=10	0.090ms	0.091ms
n=1000	1.636ms	0.854ms
n=10000	32.620ms	6.754ms
n=100000	3023.987ms	145.565ms

n が小さい場合は当然ながら両者に差はありませんが、n が 1000 を超えると今回作ったメソッドのほうが速くなり、
n=10000, n=100000 では速度差がはっきりと現れていますね。

計測結果（メモリ使用量）

	通常	高速
n=10	196KB	196KB
n=1000	1179KB	393KB
n=10000	7191KB	3269KB
n=100000	20180KB	43557KB

メモリ使用量のほうは、やり方が悪いのか、うまいこと結果が出ませんでした。
今回作成したメソッドがメモリを大食いすることは AtCoder への提出でも確認済みなので、まあこのくらいで。

今回は BigInteger型 で作りましたが、同様のメソッドを int型 や long型 で作るのは正直微妙です。
理由としては、階乗の計算は long型 でも n=30 程度で桁あふれをおこしてしまいますし、n がたったそれだけなら通常のメソッドでも今回作成したメソッドでも速度面で差がないからです。

次回はこのメソッドを利用して、 AtCoder のとある問題を力づくで解いてみたいと思います。