Hasilkan deret Fibonacci melalui perkalian matriks

Question

Saya melihat beberapa kode untuk menghasilkan $N^{th}$ Angka Fibonacci masuk $O(\log_{2}N)$ waktu, tapi saya tidak mengerti mengapa matematika berhasil.

Kode pertama-tama menginisialisasi dua matriks: $$ A =\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} , \qquad B =\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} $$ Kemudian iterasi atas bit $N$mulai dari yang paling tidak signifikan. Untuk setiap bit nomor$N$, dua hal terjadi:

1. Jika bitnya $1$, kemudian $B = B * A$
2. Kemudian $A = A * A$ bagaimanapun juga

Setelah itu, file $N^{th}$ Nomor fibonacci akan masuk $B_{0,0}$.

Mengapa ini berhasil?

Answer 1

Pertama, Anda perlu tahu itu

$$A^n=\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}$$ dan metode ini menghitung kekuatan $A$.

Sekarang, Anda dapat menghasilkan ulang dan integer $n$ dari bagian-bagiannya $b_k$, dari yang paling signifikan hingga paling tidak signifikan, berdasarkan kekambuhan

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

Mengikuti skema ini, Anda mendapatkan kekuatan $X^{m_k}$ dari sebuah matriks $X$ oleh

$$M_{-1}=M^0=I,\\M_k=X^{2m_{k-1}+b_k}=M_{k-1}^2X^{b_k}$$ dimana $X^{b_k}$ baik $I$ atau $X$.