Matris çarpımı yoluyla Fibonacci dizisi oluşturun

Question

Oluşturmak için bazı kodlar gördüm $N^{th}$ Fibonacci sayısı $O(\log_{2}N)$ zaman, ama matematiğin neden işe yaradığını anlamıyorum.

Kod önce iki matrisi başlatır: $$ A =\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} , \qquad B =\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} $$ Daha sonra, şu parçaların üzerinde yinelenir: $N$en önemsiz bitten başlayarak. Sayının her biti için$N$iki şey olur:

1. Eğer bit ise $1$, sonra $B = B * A$
2. Sonra $A = A * A$ öyle ya da böyle

Bundan sonra $N^{th}$ fibonacci numarası olacak $B_{0,0}$.

Bu neden işe yarıyor?

Answer 1

Önce bunu bilmelisin

$$A^n=\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}$$ ve bu yöntem güçlerini hesaplar $A$.

Şimdi yeniden oluşturabilir ve tam sayı yapabilirsiniz $n$ bitlerinden $b_k$yinelemeye göre en önemliden en önemsize

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

Bu düzeni takiben, güçleri elde edersiniz $X^{m_k}$ bir matrisin $X$ tarafından

$$M_{-1}=M^0=I,\\M_k=X^{2m_{k-1}+b_k}=M_{k-1}^2X^{b_k}$$ nerede $X^{b_k}$ ya $I$ veya $X$.