$u_n$をフィボナッチ数列とする. すなわち

\begin{align*}
u_0 &= 0, \quad u_1 = 1 \\
u_{n+2} &= u_n + u_{n+1}.
\end{align*}

この数列の第$n$項を求める問題を考える.

積み上げ式と呼ばれる以下のような方法がよく用いられる:

$a=0$, $b=1$とおく
$a, b = b, a + b$ という処理を$n$回繰り返す.
$a$は$u_n$と等しい.

$n$が大きい時にもっと高速に求める方法を考えてみる.

行列を用いて計算する方法もあるが, ここでは整数だけでやる方法を考えてみる.

主張

以下の式とメモ化再帰を利用して, フィボナッチ数列を計算すると $O(\log(n))$である.

\begin{align*}
u_0 &= 0, \\
u_1 &= 1, \\
u_{n} &= u_{\frac{n}{2}}^2 + 2 u_{\frac{n}{2} - 1} u_{\frac{n}{2}} & \quad (n\text{が偶数のとき}) \\
u_{n} &= 2u_{\frac{n-1}{2}}^2 + 2u_{\frac{n-1}{2} - 1}u_{\frac{n-1}{2}} + u_{\frac{n-1}{2} - 1}^2
&\quad (n\text{が奇数のとき})
\end{align*}

ソースコード

from functools import lru_cache


@lru_cache(maxsize=None)
def fib(n: int, mod=None) -> int:
    if n < 0:
        return (-1)**(n % 2) * fib(-n)
    elif n in (0, 1):
        return n

    m = n // 2
    fibm = fib(m, mod=mod)
    fibm2 = fib(m - 1, mod=mod)
    if n % 2 == 0:
        res = fibm**2 + 2 * fibm * fibm2
    else:
        res = 2 * fibm**2 + 2 * fibm * fibm2 + fibm2**2

    if mod:
        res %= mod

    return res

ただしここで, $n$が負の値の時は$(-1)^n u_{-n}$を返すようにした (一般化されたフィボナッチ数列という).

計算量の評価

式より $u_n$を$u_{\lfloor \frac{n}{2} \rfloor}$ と$u_{\lfloor \frac{n}{2} \rfloor - 1}$ から計算している.

最初の段に$u_n$を書く
nが0でも1でもなければ $n$の下の段に $\lfloor \frac{n}{2} \rfloor, \lfloor \frac{n}{2} \rfloor - 1$がそれぞれ存在しなければ追加する, という処理を再帰的に実行する.

のようにして, 段の列を作成する.

例えば $n=10$のときは

\begin{align*}
& 10 \\
& 5, 4 \\
& 2, 1 \\
& 1, 0
\end{align*}

である.

作り方からこの列の長さは$O(\log(n))$である.

それぞれの段の長さは高々3であることを示す.

まず, それぞれの段は連続する非負整数の列である.
これは帰納法で示すことができる.

今考えている列の要素のうち0でも1でもないような要素の数が1であるとき, $n$が偶数の場合と奇数の場合それぞれについて考えると

\begin{align*}
& 2k \\
& k, k-1
\end{align*}

及び

\begin{align*}
& 2k - 1 \\
& k - 1, k-2
\end{align*}

要素数が2のとき

2k, 2k-1 \\
k, k-1, k-2

及び

2k+1, 2k \\
k, k-1

要素数が3のとき

2k+1, 2k, 2k-1 \\
k, k-1, k-2

及び

2k, 2k-1, 2k-2 \\
k, k-1, k-2

となる.

いずれも長さは3以下であるから, それぞれの段の長さは高々3である.

数式部分の証明

$n$が自然数の時

\begin{align*}
u_{n} &= u_{\frac{n}{2}}^2 + 2 u_{\frac{n}{2} - 1} u_{\frac{n}{2}} & \quad (n\text{が偶数のとき}) \\
u_{n} &= 2u_{\frac{n-1}{2}}^2 + 2u_{\frac{n-1}{2} - 1}u_{\frac{n-1}{2}} + u_{\frac{n-1}{2} - 1}^2
&\quad (n\text{が3以上の奇数のとき})
\end{align*}

を示す.

フィボナッチ数の加法定理と呼ばれる以下の定理を思い出しておく:

自然数$s, t$に対して

u_{s+t} = u_{s-1}u_{t} + u_s u_{t+1}

が成り立つ(参考URL: フィボナッチ数列の加法定理).

$n$が偶数のとき:

$n = 2k$とおく. フィボナッチ数の加法定理より

\begin{align*}
u_{2k} 
&= u_{k-1}u_k + u_k u_{k+1} \\
&= u_{k-1}u_k + u_k (u_{k-1} + u_k) \\
&= u_k^2 + 2 u_{k-1}u_k.
\end{align*}

$n$が3以上の奇数のとき:

$n=2k + 1$とおく. フィボナッチ数の加法定理より

\begin{align*}
u_{2k+1}
&= u_{k + (k+1)} \\
&= u_{k-1}u_{k+1} + u_k u_{k+2} \\
&= u_{k-1}u_{k+1} + u_k (u_k + u_{k+1}) \\
&= u_k^2 + u_{k-1}u_{k+1} + u_k u_{k+1} \\
&= u_k^2 + u_{k-1}(u_{k-1} + u_k) + u_k (u_{k-1} + u_k) \\
&= 2u_k^2 + 2u_{k-1}u_k + u_{k-1}^2
\end{align*}

後は $k$を$n$に戻せば示される.