Gere a sequência de Fibonacci via multiplicação de matrizes

Aug 19 2020

Eu vi algum código para gerar o$N^{th}$Número de Fibonacci em$O(\log_{2}N)$tempo, mas não entendo por que a matemática funciona.

O código primeiro inicializa duas matrizes:$$ A =\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} , \qquad B =\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} $$Em seguida, itera sobre os bits de$N$partindo do bit menos significativo. Para cada bit do número$N$, duas coisas acontecem:

  1. Se o bit for$1$, então$B = B * A$
  2. Então$A = A * A$de qualquer jeito

Depois disso, o$N^{th}$número de fibonacci estará em$B_{0,0}$.

Por que isso funciona?

Respostas

2 YvesDaoust Aug 19 2020 at 02:51

Primeiro você precisa saber que

$$A^n=\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}$$e este método calcula as potências de$A$.

Agora, você pode gerar novamente e inteiro$n$de seus bits$b_k$, do mais significativo ao menos significativo, pela recorrência

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

Seguindo este esquema, você obtém os poderes$X^{m_k}$de uma matriz$X$por

$$M_{-1}=M^0=I,\\M_k=X^{2m_{k-1}+b_k}=M_{k-1}^2X^{b_k}$$Onde$X^{b_k}$é também$I$ou$X$.