สร้างลำดับฟีโบนักชีผ่านการคูณเมทริกซ์

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}$ หมายเลข fibonacci จะอยู่ใน $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$.