Genere la secuencia de Fibonacci a través de la multiplicación de matrices
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:
- Si el bit es$1$, después$B = B * A$
- 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
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$.