De ce contează?
Împăturește o foaie de hârtie în două: grosimea se dublează. Împătureste-o din nou: e de patru ori mai groasă. Dacă ai reuși 42 de împăturiri, teancul ar trece de Lună — pentru că fiecare pas dublează tot ce ai construit până atunci. Exponentierea rapidă folosește aceeași scurtătură: ca să ridici ceva la puterea un miliard nu faci un miliard de înmulțiri, ci dublezi exponentul pas cu pas și ajungi acolo din vreo 30 de mișcări.
Intuiția
Ridicarea la pătrat este o scară cu trepte care se dublează: din x obții
x^2, din x^2 obții x^4, apoi x^8, x^16... — fiecare pătrat dublează
exponentul. În k pași ai urcat la exponentul 2^k. Rămâne o singură întrebare:
cum combini aceste puteri „gata făcute” ca să obții exact x^n?
Răspunsul e scrierea binară a exponentului: x^13 = x^8 * x^4 * x^1, pentru că
13 = 8 + 4 + 1, adică 1101 în baza 2. Ridicând baza la pătrat succesiv obții
gratuit șirul x^1, x^2, x^4, x^8; înmulțești în rezultat doar puterile la care
bitul exponentului este 1. Orice n cere astfel cel mult 2 * log2(n) înmulțiri.
Trucul nu folosește nimic special despre numere — doar faptul că înmulțirea este
asociativă. Înmulțirea matricilor este și ea asociativă, deci aceeași schemă
calculează M^n. Iar asta deblochează Fibonacci în O(log n), numărul de
drumuri de lungime fixă într-un graf și orice recurență liniară cu n uriaș.