Candale Silviu (silviu) 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!