Сгенерируйте последовательность Фибоначчи с помощью умножения матриц

Aug 19 2020

Я видел код для генерации $N^{th}$ Число Фибоначчи в $O(\log_{2}N)$ время, но я не понимаю, почему математика работает.

Код сначала инициализирует две матрицы: $$ A =\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} , \qquad B =\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} $$ Затем он перебирает биты $N$начиная с младшего бита. Для каждого бита числа$N$, происходят две вещи:

  1. Если бит $1$, тогда $B = B * A$
  2. потом $A = A * A$ так или иначе

После этого $N^{th}$ число Фибоначчи будет в $B_{0,0}$.

Почему это работает?

Ответы

2 YvesDaoust Aug 19 2020 at 02:51

Сначала вам нужно знать, что

$$A^n=\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}$$ и этот метод вычисляет степени $A$.

Теперь вы можете повторно сгенерировать и целое число $n$ из его бит $b_k$, от наиболее значимого к наименее значительному, по повторяемости

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

Следуя этой схеме, вы получаете полномочия $X^{m_k}$ матрицы $X$ от

$$M_{-1}=M^0=I,\\M_k=X^{2m_{k-1}+b_k}=M_{k-1}^2X^{b_k}$$ где $X^{b_k}$ либо $I$ или $X$.