pythonでフィボナッチ高速化
激しく既出という気がするけど、行列を使ってフィボナッチを高速化する。
その前に、の計算を高速化するアルゴリズムを確認しておく。
def my_pow(x, n): if n == 0: return 1 elif n % 2: return x * my_pow(x, n-1) else: half_pow = my_pow(x, n/2) return half_pow * half_pow
このアルゴリズムでは、例えば、は次のように展開されて、計算される。
半分ずつにして計算するため、真っ先に考えてしまう次の展開よりも早くなる。
さて、行列を使ったフィボナッチ数の一般項の表現は次のようになる。
実は、
である。
この公式と先ほどのアルゴリズムを組み合わせればよい。
計算量は、素朴な実装が なのにたいして、となる。
あとは、行列の乗算を実装して完成。
from itertools import product def mat2_mul(X, Y): Z = [ [0, 0], [0, 0] ] for (i,j,k) in product(range(2),range(2),range(2)): Z[i][j] += X[i][k] * Y[k][j] return Z def mat2_pow(X, n): if n == 0: return [ [1, 0], [0, 1] ] elif n % 2: return mat2_mul(X, mat2_pow(X, n-1)) else: half_pow = mat2_pow(X, n/2) return mat2_mul(half_pow, half_pow) def fib(n): if n == 0: return 0 else: F = [ [0, 1], [1, 1] ] return mat2_pow(F, n-1)[1][1]
なお、ここでは(n-1)乗までの計算でとどめている。
先ほども書いたように、(n-1)乗までで、すでに第n項は出ている。