行列乗算を介してフィボナッチ数列を生成する

Question

私は生成するためのいくつかのコードを見ました $N^{th}$ のフィボナッチ数 $O(\log_{2}N)$ 時間ですが、なぜ数学が機能するのかわかりません。

コードは最初に2つの行列を初期化します。 $$ A =\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} , \qquad B =\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} $$ 次に、のビットを繰り返し処理します $N$最下位ビットから開始します。数字の各ビットについて$N$、2つのことが起こります：

1. ビットが $1$、その後 $B = B * A$
2. 次に $A = A * A$ どちらにしても

その後、 $N^{th}$ フィボナッチ数は $B_{0,0}$。

なぜこれが機能するのですか？

Answer 1

まず、それを知る必要があります

$$A^n=\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}$$ このメソッドはの力を計算します $A$。

今、あなたは再生成して整数にすることができます $n$ そのビットから $b_k$、最も重要なものから最も重要でないものへ、再発による

$$m_{-1}=0,\\m_k=2m_{k-1}+b_k.$$

このスキームに従って、あなたは力を手に入れます $X^{m_k}$ 行列の $X$ 沿って

$$M_{-1}=M^0=I,\\M_k=X^{2m_{k-1}+b_k}=M_{k-1}^2X^{b_k}$$ どこ $X^{b_k}$ どちらかです $I$ または $X$。