EeBlog(テクニカルブログ)

フィボナッチ数

フィボナッチ数という数をご存知でしょうか。今回はフィボナッチ数を求めるアルゴリズムについて考察してみます。
まずフィボナッチ数とは次のように定義される数のことです。

n番目のフィボナッチ数を F(n) として

1.F(0) = 0
2.F(1) = 1
3.F(n) = F(n – 1) + F(n – 2)
また、フィボナッチ数の性質として2の連続するフィボナッチ数の比は n が無限に増加するに従って黄金比に漸近します。

アルゴリズム①
ではまず、n 番目のフィボナッチ数を求めるアルゴリズムを、フィボナッチ数の定義からそのまま記述します。

public static BigInteger fibonacci0(int n) {
		if (n == 0) {
			return ZERO;
		} else if (n == 1) {
			return ONE;
		} else {
			return fibonacci0(n - 1).add(fibonacci0(n - 2));
		}
	}

フィボナッチ数はすぐに大きくなるので BigInteger を使用して桁溢れしないようにしています。

これでフィボナッチ数を求めることができるのですが、このアルゴリズムは非常に遅いです。n = 40 ぐらいでもうかなり遅いはずです。 n = 50 で呼び出せばしばらくは戻ってこないでしょう。

このアルゴリズムが遅い理由はメソッドのなかで自分自身を呼び出す再帰呼び出しが2回行われているからです。このためこのアルゴリズムはフィボナッチ数を求めるのに O(PHI^n)、(PHI は黄金比、およそ 1.618) の時間がかかります。

アルゴリズム②

フィボナッチ数列は n 番目のフィボナッチ数を求めるためには n – 1 番目と n – 2 番目のフィボナッチ数が必要ですが、逆に言うと 0 から n 番目までのフィボナッチ数が求まっているときに n + 1 番目のフィボナッチ数を求めるには、 n 番目と n – 1 番目のフィボナッチ数を加算すれば良いわけです。つまりフィボナッチ数を 0 番目から順番に求めていき、このときに２つ前と2つ前のフィボナッチ数を覚えておけばいいのです。

private static BigInteger fibonacci2Helper(BigInteger a, BigInteger b, int n) {
		if (n == 0) {
			return b;
		} else {

			return fibonacci2Helper(a.add(b), a, n - 1);
		}
	}
	public static BigInteger fibonacci2(int n) {
		return fibonacci2Helper(ONE, ZERO, n);
	}

１つ前と2つ前のフィボナッチ数を覚えておきながら再帰するためにヘルパーメソッドを利用しています。

これでフィボナッチ数を O(n) で求めることができるようになりました。

さきほどのアルゴリズムでは n = 50 のフィボナッチ数を求めるには途方もなく時間がかりますが、このアルゴリズムでは一瞬です。おそらく n = 10000 でもまだ余裕です。n = 100000 くらいになると少し遅くなってくるのではないでしょうか。

アルゴリズム③

アルゴリズム②では1つ前と2つ前のフィボナッチ数を覚えておいて O(n) で計算できるようにしましたが、このようなアルゴリズムの工夫をしなくてもメモ化 (memoization、memorization ではない) というテクニックを使うと、二重再帰呼び出しがあっても O(n) で計算できるようになります。

private static BigInteger[] memo = {ZERO, ONE};
public static BigInteger fibonacci3(int n) {
     if (n >= memo.length) {
	int newSize = memo.length * 2;
	memo = Arrays.copyOf(memo, (newSize > (n + 1))?newSize:(n + 1));
     }
     if (memo[n] == null) {
     memo[n] = fibonacci3(n - 1).add(fibonacci3(n - 2));
     }
     return memo[n];
}

これは一度求めた値をすべて保存しておき、2度目からは保存しておいた値を返すようにしています。これによってある引数の値での1度目の呼び出しでは O(n) ですが、同じ引数の値での 2度目以降の呼び出しは O(1) になります。

ただし、これには呼び出し結果を保存するためのメモリ領域が必要です。

アルゴリズム④

フィボナッチ数を求めるのに O(PHI^n) から O(n) になってずいぶん速くなりましたが、アルゴリズム②を改良することでさらに高速化することが可能です。

アルゴリズム②は次のような変換手続きを n 回繰り返すことで b が求めたいフィボナッチ数になるというアルゴリズムでした。

a ← a + b
b ← a

ここで、この変換を次のような変換 Tpq の p = 0, q = 1 であるときの特殊なケースであるとみなします。

a ← aq + bq + ap
b ← bp + aq

そしてこの変換 Tpq を a と b に対して2回行う変換を Tp’q’ とします。Tp’q’ はTpq 変換を2回行った結果と同じ結果を求める変換なので、この変換では最終的な答えを求めるのに変換を行う回数が、変換 Tpq の半分になります。

変換 Tp’q’ は

1回目

a’ ← aq + bq + ap

b’ ← bp + aq

2回目

a” ← a’q + b’q + a’p

b” ← b’p + a’q

a0, b0 を a, b に展開し整理

a” ← a(2pq + p^2) + b(2pq + p^2) +a(p^2 + q^2)

b” ← b(p^2 + q^2) + a(2pq + p^2)

になり、したがって p’ = p^2 + q^2, q’ = 2pq + p^2 になります。
これを利用したフィボナッチ数を求めるアルゴリズムは次のとおりです。

private static boolean isEven(int n) {
		return (n % 2) == 0;
	}
	private static BigInteger fibonacci4Helper(
			BigInteger a, BigInteger b,
			BigInteger p, BigInteger q, int n) {
		if (n == 0) {
			return b;
		} else if (isEven(n)) {
			BigInteger p2 = p.multiply(p);
			BigInteger q2 = q.multiply(q);
			BigInteger pq = p.multiply(q);
			return fibonacci4Helper(a, b, 
                                 p2.add(q2), TWO.multiply(pq).add(q2), n / 2);
		} else {
			BigInteger ap = a.multiply(p);
			BigInteger aq = a.multiply(q);
			BigInteger bp = b.multiply(p);
			BigInteger bq = b.multiply(q);
			return fibonacci4Helper(aq.add(bq).add(ap), 
                                                     aq.add(bp), p, q, n - 1);
		}
	}
	public static BigInteger fibonacci4(int n) {
		return fibonacci4Helper(ONE, ZERO, ZERO, ONE, n);
	}

このアルゴリズムではフィボナッチ数を O(log n) で求めることができます。
このアルゴリズムでは n = 1000000 くらいまでならそこそこの時間で求めることができます。(ここまでくると、BigInteger の加減乗除が O(n) や O(2^n) で効いてくるのであんまり速くなりません)

まとめ

フィボナッチ数を求めるアルゴリズムを色々検討してきました。ソートアルゴリズムなどは有名で色々種類がありますが、フィボナッチ数のような些細な問題でも考え出すといろいろなアルゴリズムが考えられるのはなかなかおもしろいものです。
実はフィボナッチ数を求める方法は他にもありますが、これは自分で調べて実装してみてください。

2010年3月10日 | カテゴリー：アルゴリズム

│トップ│