今回はフィボナッチ数を対数時間で求めるプログラムについてです。

（ Wikipedia より）

フィボナッチ数とは、次の漸化式で表せる数列です。

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (n >= 2)

実際に各値を求めると次のような数値になります。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

Wikipedia には次のような一文があります。

フィボナッチ数（フィボナッチすう、英: Fibonacci number）は、イタリアの数学者レオナルド・フィボナッチ（ピサのレオナルド）にちなんで名付けられた数である。

• フィボナッチ数 - Wikipedia
• Fibonacci - Wikipedia

なんでも、 12 世紀頃の数学者であり「フィボナッチ」（ボナッチの息子）と（後に）呼ばれた、イタリアのレオナルドさん発案だそうです。

余談ですが、「レオナルド」はイタリアあたりの歴史にやたらに登場しますね。日本でいう「ごんべえ」的な感じでしょうか。

それはさておき。

フィボナッチ数の値は解析的に求めることもできますが、プログラミングの課題としては、再帰アルゴリズムあるいは動的計画法を使って解くことが求められることが多いようです。

まずはロジックが最もシンプルな線形時間でのアプローチを先に見てみましょう。

線形時間での求解

単純なループを使った動的計画法アプローチでは、線形時間 O(n) で解くことができます。

• https://gist.github.com/gh640/a69d2018801ce3578868375a060f1e78

これは直感的な求め方ですね。続いて対数時間で求めるアプローチです。

対数時間での求解

フィボナッチ数は直感に反し、対数時間 O(log(n)) で求めることができます。

ポイントは次のとおりです。

1. 行列で考えた場合、フィボナッチ数の漸化式は F(n) = P * F(n - 1)（ただし P は ((1, 1), (1, 0) という行列）で表せる。
2. 結果、 F(n) は F(n) = P^n * (1, 0)^T で求めることができる。
3. ミソは P^n の計算で、これは単純に P を n 回積を繰り返して求めることもできるが、例えば n = 2^m となる場合（例えば n = 64 なら m = 6 ）にかぎると、 P^64 = (P^32)^2 = ((P^16)^2)^2 = (((P^8)^2)^2)^2 = ((((P^4)^2)^2)^2)^2 = (((((P^2)^2)^2)^2)^2)^2 ということで、 2 乗を 6 回繰り返す形でも求めることができる（つまり指数時間で求められる）。これは 63 回積を繰り返すより断然早い。
4. n = 2^m とならない n については、 n = 2^m1 + 2^m2 + 2^m3 + ... という形に分解することで（要は 2 進数表現にすることによって）各部を 2^m の形に表すことができる。この事実を利用すると、 P^n = P^(2^m1 + 2^m2 + 2^m3 + ...) = P^(2^m1) * P^(2^m2) * P^(2^m3) * ... で求められる。

詳細のロジックに興味のある方は、次のページの解説がとても丁寧でわかりやすいのでそちらをご覧になってみてください。

• The Nth Fibonacci Number in O(log N)

実際のサンプルコードは次のとおりです。

• https://gist.github.com/gh640/3ae714c2e83848af4165a24a155b78ac

コード上のポイントは次のとおりです。

• フィボナッチ数を求める関数は get_fibonacci() で、それ以外の関数はすべてヘルパー関数です。
• if __name__ == '__main__': 以下の部分はすべてテストコードです。
• 上の 4. の 2 の乗数への分解を行う関数は get_2exponent_series() です。
• 上の 3. の部分を担う関数は pow_matrix() です。
• 行列の積の計算は multiply_matrix() で行っています。単純な 2 x 2 行列の計算なので、ライブラリは使わずそのまま計算しています。間違いやすいのでケアレスミスに注意が必要です。
• やや本筋から外れる、キャッシングと畳み込みの計算には標準ライブラリ functools の lru_cache() と reduce() を使っています。

以前の「ハノイの塔」のサンプルと同じく、ホワイトボードコーディングの本の中に出てきたので個人的なエクササイズを兼ねて書いてみました。

この話題（「フィボナッチ数を対数時間で求める方法」）については学生時代にちらっと学んだことがある気がするのですが、その詳細は完全に忘れてしまっていたので、今回改めて調べて「おぉ、これはすごい！」ととても感動しました（笑）。

再帰や動的計画法は「問題の本質をいかにシンプルな形で捉え抽出することができるか」がポイントで、このあたりは汎用の問題解決能力とも直結する気がします。私はこのあたりは特段苦手というわけではありませんが、「ものすごく得意」「閃きまくって仕方がない！」というわけでもないので、こういう問題解決が得意な人を見るとうらやましくなります。