De ce contează?
Cineva îți cere al 1.000.000.000.000.000.000-lea termen Fibonacci (adică
F(10^18), modulo un număr prim). Dacă îl calculezi termen cu termen, ai nevoie
de un miliard de miliarde de adunări — calculatorul ar muri de bătrânețe înainte
să termine. Și totuși răspunsul iese într-o clipită: scrii recurența ca o
matrice mică și o ridici la puterea 10^18 în doar ~60 de pași.
Intuiția
Fibonacci spune că fiecare termen e suma ultimelor două: F(i) = F(i-1) + F(i-2).
Ca să faci un pas înainte îți trebuie doar fereastra ultimelor două valori
(F(i-1), F(i-2)). Un pas înainte e mereu aceeași transformare a ferestrei — și
„aceeași transformare aplicată unei perechi de numere” se scrie cu o matrice.
Pasul recurenței = o înmulțire cu aceeași matrice de tranziție T, fixă.
Deci n pași = T^n aplicat ferestrei de start. Iar T^n nu se calculează în
n pași, ci în log n, prin ridicare la pătrat — exact mecanica din lecția
anterioară, Ridicarea matricilor la putere în timp logaritmic. Aici înveți
partea nouă: cum modelezi recurența ca matrice.