Сгенерируйте последовательность Фибоначчи с помощью умножения матриц
Я видел код для генерации $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$, тогда $B = B * A$
- потом $A = A * A$ так или иначе
После этого $N^{th}$ число Фибоначчи будет в $B_{0,0}$.
Почему это работает?
Ответы
Сначала вам нужно знать, что
$$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$.