フィボナッチ数列 (Fibonacci Sequence)

概要

フィボナッチ数列 \(a_{i+1} = a_i + a_{i-1}\) (\(a_0 = 0\), \(a_1 = 1\)) について \(a_N\) を求める。

\(a_0, a_1\) から順番に \(a_2, a_3, ..., a_N\) を計算することで \(O(N)\) で計算できる。

また、 \(a_{i+1}, a_i, a_{i-1}\) の関係を行列を用いて以下のように表せるため、行列累乗によって \(a_N\) を \(O(\log N)\) で計算できる。

\( \displaystyle \left( \begin{array}{c} a_{n+1} \\ a_n \end{array} \right) = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{c} a_n \\ a_{n-1} \end{array} \right) = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)^n \left( \begin{array}{c} a_1 \\ a_0 \end{array} \right)\)

実装

# O(N)
def fibonacci1(N, M):
    a = 0; b = 1
    for _ in range(N):
        a, b = b, (a + b) % M
    return a

# O(log N)
def fibonacci2(N, M):
    # R = [1, 0; 0, 1]
    RA = RD = 1; RB = RC = 0
    # X = [1, 1; 1, 0]
    XA = XB = XC = 1; XD = 0
    while N:
        if N & 1:
            # R <- RX
            RA, RB, RC, RD = (RA*XA + RB*XC) % M, (RA*XB + RB*XD) % M, (RC*XA + RD*XC) % M, (RC*XB + RD*XD) % M
        # X <- XX
        XA, XB, XC, XD = (XA**2 + XB*XC) % M, XB*(XA + XD) % M, XC*(XA + XD) % M, (XB*XC + XD**2) % M
        N >>= 1
    return RC