Générer une séquence de Fibonacci via la multiplication matricielle
J'ai vu du code pour générer le$N^{th}$Nombre de Fibonacci en$O(\log_{2}N)$temps, mais je ne comprends pas pourquoi les calculs fonctionnent.
Le code initialise d'abord deux matrices :$$ A =\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} , \qquad B =\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} $$Il parcourt ensuite les bits de$N$en partant du bit le moins significatif. Pour chaque bit du nombre$N$, deux choses se produisent :
- Si le bit est$1$, alors$B = B * A$
- Alors$A = A * A$dans les deux cas
Après cela, le$N^{th}$le nombre de fibonacci sera dans$B_{0,0}$.
Pourquoi cela fonctionne-t-il ?
Réponses
Vous devez d'abord savoir que
$$A^n=\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}$$et cette méthode calcule les puissances de$A$.
Maintenant, vous pouvez re-générer et entier$n$de ses morceaux$b_k$, du plus significatif au moins significatif, par la récurrence
$$m_{-1}=0,\\m_k=2m_{k-1}+b_k.$$
Suite à ce schéma, vous obtenez les pouvoirs$X^{m_k}$d'une matrice$X$par
$$M_{-1}=M^0=I,\\M_k=X^{2m_{k-1}+b_k}=M_{k-1}^2X^{b_k}$$où$X^{b_k}$est soit$I$ou$X$.