행렬 곱셈을 통해 피보나치 수열 생성

Question

나는 생성하는 코드를 보았다 $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}$.

왜 이것이 작동합니까?

Answer 1

먼저 알아야합니다.

$$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$.