Introducere

Șirul lui Fibonacci este definit astfel:

$$ F_n = \begin{cases}
1& \text{dacă } n = 1 \text{ sau } n = 2 ,\\
F_{n-1} + F_{n-2} & \text{dacă } n > 2.
\end{cases} $$

Pentru a determina al n-termen a șirului putem folosi diverse metode. Acest articol prezintă un algoritm de complexitate \(O(n)\) care determină al n-lea termen.

Prezentul articol prezintă un algoritm de complexitate logaritmică, bazat pe înmulțirea rapidă a matricelor.

Matrice Fibonacci

Considerăm următoarea matrice: \( Q = \left( \begin{matrix} 1& 1\\ 1& 0\end{matrix} \right) \). Dacă extindem șirul lui Fibonacii cu încă un element, \( F_0 = 0 \), observăm că: \( Q = \left( \begin{matrix} F_2& F_1\\ F_1& F_0\end{matrix} \right) \). Să calculăm \(Q^2\) și \(Q^3\):

$$ \begin{align} Q^2 & = Q \times Q \\ & = \left( \begin{matrix} F_2& F_1\\ F_1& F_0\end{matrix} \right) \times \left( \begin{matrix} 1& 1\\ 1& 0\end{matrix} \right)\\ & = \left( \begin{matrix} F_2 \cdot 1 + F_1 \cdot 1& F_2 \cdot 1 + F_1 \cdot 0 \\ F_1 \cdot 1 + F_0 \cdot 1& F_1 \cdot 1 + F_0 \cdot 0 \end{matrix} \right) \\ & = \left( \begin{matrix} F_2 + F_1 & F_2 \\ F_1 + F_0 & F_1 \end{matrix} \right) \\ & = \left( \begin{matrix} F_3 & F_2 \\ F_2 & F_1 \end{matrix} \right) \\
\end{align}
$$

Similar:

$$ \begin{align} Q^3 & = Q^2 \times Q \\ & = \left( \begin{matrix} F_3 & F_2\\ F_2 & F_1\end{matrix} \right) \times \left( \begin{matrix} 1& 1\\ 1& 0\end{matrix} \right)\\ & = \left( \begin{matrix} F_3 \cdot 1 + F_2 \cdot 1& F_3 \cdot 1 + F_2 \cdot 0 \\ F_2 \cdot 1 + F_1 \cdot 1& F_2 \cdot 1 + F_1 \cdot 0 \end{matrix} \right) \\ & = \left( \begin{matrix} F_3 + F_2 & F_3 \\ F_2 + F_1 & F_2 \end{matrix} \right) \\ & = \left( \begin{matrix} F_4 & F_3 \\ F_3 & F_2 \end{matrix} \right) \\
\end{align}
$$

Observăm că \( Q^n = \left( \begin{matrix} F_{n+1}& F_n\\ F_n& F_{n-1}\end{matrix} \right) \), lucru ușor de demonstrat prin inducție matematică.

Concluzie: Dacă \( Q = \left( \begin{matrix} 1& 1\\ 1& 0\end{matrix} \right) \), atunci \( Q^n = \left( \begin{matrix} F_{n+1}& F_n\\ F_n& F_{n-1}\end{matrix} \right) \).

Algoritm

Pentru a determina \(F_n\), considerăm matricea \( Q = \left( \begin{matrix} 1& 1\\ 1& 0\end{matrix} \right) \), pe care o ridicăm la puterea n. Pentru a efectua repede calculele, folosim exponențierea rapidă.

Problema #Fibonacci2 cere determinarea celui de-al n-lea termen al șirului lui Fibonacii, modulo 666013. Succes!

Bibliografie