♥ 余談: さらに高速な Fibonacci 数
先ほど示したアルゴリズムは単純で魅力的でしたが、Fibonacci 数を計算する最速のアルゴリズムではありません。Fibbonacci 数を定義する再帰方程式を次のように行列の式として表すと、これまでより速いアルゴリズムが作れます: \[ \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} y \\ x + y \end{bmatrix} \] この式を言い換えると、二次元ベクトルに行列 \(\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\) を掛けることが \(\textsc{IterFibo2}\) の for ループを一回進めるのとちょうど同じ効果を持っているということです。よって行列を \(n\) 回掛ければ for ループを \(n\) 回反復できます: \[ \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^n \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} F_{n-1} \\ F_{n} \end{bmatrix} \] つまり \(n\) 個目の Fibonacci 数を計算する問題は \(\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\) の \(n\) 乗を計算する問題となります。二乗を反復して用いれば1、\(n\) 乗の計算には \(O(\log n)\) 回の "乗算" しか必要になりません。今の問題では "乗算" が \(2 \times 2\) の行列乗算であり、この行列乗算は定数回数の整数乗算と整数加算からなるので、\(F_{n}\) は \(\pmb{O(\log n)}\) 回の整数演算で計算できます。
行列を使わなくても、\(F_{n} =\) \(F_{m}F_{n - m - 1} + F_{m+1}F_{n-m}\) という任意の整数 \(m, n\) に対して成り立つ等式 (証明は帰納法) を利用すれば同じ性能を達成できます。この式からは次に示す隣り合う Fibonacci 数に関する相互再帰的な等式が得られます。この等式は Édouard Lucas (エドゥアール・リュカ) によって 1898 年に初めて示されました: \[ \begin{aligned} F_{2n-1} & = F_{n-1}^{2} + F_{n}^{2} \\ F_{2n} & = F_{n}(F_{n-1} + F_{n+1}) = F_{n}(2F_{n-1} + F_{n}) \end{aligned} \] (行列の二乗を使ったアルゴリズムからこの相互再帰的な方程式を得ることもできます) この式から次のアルゴリズムがすぐに得られます:
⟨⟨\(F_{n-1}, F_{n}\) の組を計算する⟩⟩
procedure \(\texttt{FastRecFibo}\)(\(n\))
if \(n = 1\) then
return \(0, 1\)
else
\(m \leftarrow \lfloor n/2 \rfloor\)
\(\mathit{hprv},\ \mathit{hcur} \leftarrow\)\(\texttt{FastRecFibo}\)(\(m\)) \(\quad \phantom{,}\) ⟨⟨\(F_{m-1},\ F_{m}\)⟩⟩
\(\mathit{prev} \leftarrow \mathit{hprv}^{2} + \mathit{hcur}^{2}\) \(\quad \hphantom{,,,,,,,,,,}\) ⟨⟨\(F_{2m-1}\)⟩⟩
\(\mathit{curr} \leftarrow \mathit{hcur} \cdot (2 \cdot \mathit{hprv} + \mathit{hcur})\) \(\quad \phantom{..}\) ⟨⟨\(F_{2m}\)⟩⟩
\(\mathit{next} \leftarrow \mathit{prev} + \mathit{curr}\) \(\quad \, \hphantom{,,,,,,,,,,,,}\) ⟨⟨\(F_{2m+1}\)⟩⟩
if \(n\) が偶数 then
return \(\mathit{prev},\ \mathit{curr}\)
else
return \(\mathit{curr},\ \mathit{next}\)
通常の再帰木の方法を使うと、このアルゴリズムが整数演算を \(O(\log n)\) 回行うことが分かります。
ループを使ったアルゴリズムは最初の再帰的なアルゴリズムを指数的に高速化したものでしたが、それをさらに指数的に高速化できました。そうですよね？
うわ！ たいして速くない！
正確に言うと、実はそうではありません。Fibonacci 数は指数的に大きくなり、\(n\) 番目の Fibonacci 数は 10 進表記で \(n \log \phi \approx n / 5\) 桁、二進表記で \(n \log_{2} \phi \approx 2n/3\) 桁の数となります。このため \(F_{n}\) を対数時間で計算するのは不可能です ――答えを書くだけで \(\Omega(n)\) 時間かかるのですから！
このパラドックスを解く鍵は、任意精度の算術を定数時間で行うことはできないという事実にあります。 \(M(n)\) で \(n\) 桁の数を掛けるのにかかる時間を表すことにすると、\(\textsc{FastRecFibo}\) の実行時間は再帰方程式 \(T(n) = T(\lfloor n/2 \rfloor) + M(n)\) を満たします。再帰木を書くと \(\pmb{T(n) = O(M(n))}\) が分かります。整数乗算の (2019 年時点で) 最速の実行時間は \(O(n \log n)\) なので、この値が Fibonacci 数を計算する (2019 年時点で) 最速の実行時間となります。
それではこのアルゴリズムは for ループを使った "線形" のアルゴリズムよりも遅いのでしょうか？ 答えは No です。整数の足し算も常に定数時間で行えるわけではないからです。二つの \(n\) 桁の整数の加算は \(O(n)\) 時間かかるので、for ループを使ったアルゴリズム \(\textsc{IterFibo}\) と \(\textsc{IterFibo2}\) の実行時間は \(\pmb{O(n^{2})}\) です (このことを示せますか？)。 そのため、 \(\textsc{FastRecFibo}\) は for ループを使ったアルゴリズムよりも格段に高速です。ただし指数的に高速ではありません。
最初にあげた再帰的なアルゴリズムでは、任意精度の整数演算による追加のコストは大量の再帰呼び出しに隠れます。つまり正しい再帰方程式は \(T(n) =\) \(T(n - 1) + T(n - 2) + O(n)\) ですが、答えは \(T(n) = O(\phi^{n})\) のままです。
-
Chandaḥśāstra で Piṅgala が 2 のべきに対して使ったのと同じやり方です。[return]