フィボナッチ数列100万番目を求めるアプローチ

素朴な実装の限界

まず、単純なループで考える。

def fib_naive(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

$n = 10^6$ の場合、ループ自体は100万回で終わる。ただし問題は多倍長整数の加算コストである。 $F_{10^6}$ は約20万桁になるため、加算1回が $O(\text{桁数})$ かかる。結果的に $O(n \cdot \text{桁数})$ となり、実測で数十秒〜数分オーダー。

行列累乗法

フィボナッチの漸化式を行列で表現：

 $\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix}$

これを展開すると：

 $\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}$

行列の累乗は繰り返し二乗法で $O(\log n)$ 回の行列乗算で計算可能。

def matrix_mult(A, B):
    return [
        [A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
        [A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]
    ]

def matrix_pow(M, n):
    result = [[1, 0], [0, 1]]  # 単位行列
    while n:
        if n & 1:
            result = matrix_mult(result, M)
        M = matrix_mult(M, M)
        n >>= 1
    return result

def fib_matrix(n):
    if n == 0:
        return 0
    M = [[1, 1], [1, 0]]
    return matrix_pow(M, n)[0][1]

計算量は $O(\log n)$ 回の行列乗算。ただし各要素が巨大整数なので、乗算コストを考慮すると単純な $O(\log n)$ ではない。

高速倍化法（Fast Doubling）

行列累乗から導出される以下の恒等式を直接使う：

 $F_{2k} = F_k \cdot (2F_{k+1} - F_k)$

 $F_{2k+1} = F_k^2 + F_{k+1}^2$

def fib_fast_doubling(n):
    def fib_pair(n):
        """(F_n, F_{n+1}) を返す"""
        if n == 0:
            return (0, 1)

        f_k, f_k1 = fib_pair(n >> 1)
        f_2k = f_k * (2 * f_k1 - f_k)
        f_2k1 = f_k * f_k + f_k1 * f_k1

        if n & 1:
            return (f_2k1, f_2k + f_2k1)
        else:
            return (f_2k, f_2k1)

    return fib_pair(n)[0]

2x2行列の4要素ではなく2要素だけ追跡するため、行列累乗と本質的に同じだが定数倍で有利である。

図を読み込み中...

計算量の詳細分析

$F_n$ の桁数は $O(n)$ である（ $F_n \approx \phi^n / \sqrt{5}$ より）。

手法	乗算/加算回数	多倍長乗算コスト込み
素朴ループ	$O(n)$	$O(n^2)$ ～ $O(n^2 / \log n)$ *
行列累乗	$O(\log n)$	$O(M(n) \log n)$
Fast Doubling	$O(\log n)$	$O(M(n) \log n)$

*Pythonの多倍長整数はKaratsuba法を使うため、乗算は $O(n^{1.585})$ 程度。

$M(n)$ は $n$ 桁の乗算コスト。Karatsuba なら $O(n^{1.585})$ 、FFT系なら $O(n \log n)$ 近辺。

図を読み込み中...

実測値の目安

$n = 10^6$ の場合（Python 3、一般的なPC）：

素朴ループ: 30〜60秒
Fast Doubling: 1〜3秒

約20倍以上の高速化。GMP（gmpy2）を使えばさらに高速。

import gmpy2

def fib_gmpy(n):
    return int(gmpy2.fib(n))

gmpy2は内部で最適化されたアルゴリズムを使用しており、100万番目でも1秒未満。

面接での補足ポイント

「なぜ行列累乗が速いのか」への回答

素朴な方法は $n$ 回の加算を逐次実行する。行列累乗は「倍々で進む」ことで $\log n$ ステップに圧縮する。各ステップでの計算量は増えるが、ステップ数の削減効果が圧倒的である。

「メモ化再帰との比較は？」

メモ化再帰は $O(n)$ のメモリを消費し、かつ $O(n)$ 回の加算が必要である。Fast Doublingは $O(\log n)$ のスタック深さで済む。

「mod を取る場合は？」

$F_n \mod m$ を求める場合、行列累乗/Fast Doublingがそのまま適用可能である。各演算後にmodを取れば、整数サイズが $O(\log m)$ に抑えられ、純粋に $O(\log n)$ となる。競プロでよく出るパターンである。

「周期性（ピサノ周期）は使える？」

$F_n \mod m$ には周期 $\pi(m)$ が存在する。 $m$ が小さければ周期を求めてから $n \mod \pi(m)$ で計算すると速い。ただし $\pi(m)$ の上界は $6m$ なので、 $m$ が大きいと周期探索自体がコストになる。

まとめ

観点	推奨
実装のシンプルさ	Fast Doubling
最速	gmpy2.fib()
mod付き	Fast Doubling + mod
面接での説明	行列累乗の導出 → Fast Doublingへの簡略化

100万番目程度であればFast Doublingで十分実用的である。それ以上（10億など）になると、SchönhageーStrassen法などさらに高度な多倍長演算の最適化が効いてくる。