フィボナッチ数の計算

久しぶり、雷鳴です。一昨年７月から社会人になった。いろいろ忙しい（たぶん）ので記事を全然書いてないorz

アルゴリズムに上手なプログラマーはわりに人気のようだ。でも自分はアルゴリズムに下手なんだ。
だからすこしアルゴリズム技が進めばいいと思って、日曜にMITの授業録画（の中国語訳バージョン）を見て勉強した。

その中で新しいフィボナッチ数の計算方法ははじめて知った：
行列

[ 1 1 ]

[ 1 0 ]

を累乗して、その左上の数は「累乗の回数」番目のフィボナッチ数。

累乗も、そのまま a * a * a * a * ...　より早い方法がある。
行列[(1 1) (1 0)]はAにして、累乗の回数はnにする。
そしてnはバイナリ表示の方法で、n = b0 * 2^0 + b1 * 2^1 + b2 * 2^2 + b3 * 2^3 + ... にする。
（そのなかで b0, b1, b2, b3...∈{ 0, 1 }）
だから A^n = A^(b1 * 2^0) * A^(b2 * 2^1) * A^(b3 * 2^2) * ...
b[x]=0の時、A^(b[x] * 2^x) = A^0 = I
また任意行列Bは IB = B、BI = B だ。
だからこんなループ

R ← I

An ← A

while n ≠ 0

    b = n mod 2

    if b == 1 then

        R ← R * An

    An ← An * An

    n ← (n - b) / 2

は、Aのn回累乗を計算できる。

さっそくpythonでそんなプログラムを書いてみようと、
https://github.com/sorayuki/practise/blob/master/Fibonacci.py
こうなった。

この方法で、第２００００番目のフィボナッチ数は、乗法１６０回と加法１６０回でゲットした