Genere la secuencia de Fibonacci a través de la multiplicación de matrices

Aug 19 2020

Vi un código para generar el$N^{th}$numero de fibonacci en$O(\log_{2}N)$tiempo, pero no entiendo por qué funcionan las matemáticas.

El código primero inicializa dos matrices:$$ A =\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} , \qquad B =\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} $$Luego itera sobre los bits de$N$empezando por el bit menos significativo. Para cada bit del número$N$, suceden dos cosas:

  1. Si el bit es$1$, después$B = B * A$
  2. Después$A = A * A$de todas formas

Después de eso, el$N^{th}$el número de fibonacci estará en$B_{0,0}$.

¿Por qué funciona esto?

Respuestas

2 YvesDaoust Aug 19 2020 at 02:51

Primero necesitas saber que

$$A^n=\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}$$y este método calcula las potencias de$A$.

Ahora, puede volver a generar y entero$n$de sus pedacitos$b_k$, de más significativo a menos significativo, por la recurrencia

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

Siguiendo este esquema, obtienes los poderes$X^{m_k}$de una matriz$X$por

$$M_{-1}=M^0=I,\\M_k=X^{2m_{k-1}+b_k}=M_{k-1}^2X^{b_k}$$dónde$X^{b_k}$es cualquiera$I$o$X$.