studies

いろいろ勉強用備忘録的な感じ

pythonでフィボナッチ高速化

激しく既出という気がするけど、行列を使ってフィボナッチを高速化する。

その前に、 x^nの計算を高速化するアルゴリズムを確認しておく。

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

このアルゴリズムでは、例えば、 3^9は次のように展開されて、計算される。
 3^9 = 3 * 3^8 = 3 * (3^4)^2 = 3 * ((3^2)^2)^2

半分ずつにして計算するため、真っ先に考えてしまう次の展開よりも早くなる。
 3^9 = 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3

さて、行列を使ったフィボナッチ数の一般項の表現は次のようになる。
 fib_n = {F^n}_{1, 2} \hspace{10pt} where \space F = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}
実は、
 F^n = \begin{pmatrix} fib_{n-1} & fib_n \\ fib_n & fib_{n+1} \end{pmatrix}
である。

この公式と先ほどのアルゴリズムを組み合わせればよい。
計算量は、素朴な実装が  O(e^n)なのにたいして、O(\log{n})となる。

あとは、行列の乗算を実装して完成。

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項は出ている。