Genera sequenza di Fibonacci tramite moltiplicazione di matrici

Question

Ho visto del codice per generare il file$N^{th}$Numero di Fibonacci dentro$O(\log_{2}N)$tempo, ma non capisco perché la matematica funzioni.

Il codice prima inizializza due matrici:$$ A =\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} , \qquad B =\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} $$Quindi itera sui bit di$N$partendo dal bit meno significativo. Per ogni bit del numero$N$, accadono due cose:

1. Se il bit è$1$, poi$B = B * A$
2. Quindi$A = A * A$in entrambi i casi

Dopodiché, il$N^{th}$ci sarà il numero di fibonacci$B_{0,0}$.

Perché funziona?

Answer 1

Per prima cosa devi saperlo

$$A^n=\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}$$e questo metodo calcola le potenze di$A$.

Ora puoi rigenerare e integer$n$dai suoi pezzi$b_k$, dal più significativo al meno significativo, in base alla ricorrenza

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

Seguendo questo schema si ottengono i poteri$X^{m_k}$di una matrice$X$di

$$M_{-1}=M^0=I,\\M_k=X^{2m_{k-1}+b_k}=M_{k-1}^2X^{b_k}$$dove$X^{b_k}$è o$I$o$X$.