Générer une séquence de Fibonacci via la multiplication matricielle

Aug 19 2020

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 :

  1. Si le bit est$1$, alors$B = B * A$
  2. 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

2 YvesDaoust Aug 19 2020 at 02:51

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}$$$X^{b_k}$est soit$I$ou$X$.