Ridicare la putere în timp logaritmic

Intuiția

Ca să calculezi $a^n$, prima idee e să înmulțești $a$ cu el însuși de $n$ ori — exact ca adăugarea straturilor unul câte unul. Dar $a^n$ se poate sparge în jumătăți: $a^{10} = a^5 \cdot a^5 = (a^5)^2$. Dacă știi deja $a^5$, mai faci o singură înmulțire (ridicarea la pătrat) și ai $a^{10}$ — exact ca împăturirea care dublează grosimea. Repetând ideea, exponentul se înjumătățește la fiecare pas, așa că ajungi de la $n$ pași la doar $\log_2 n$: pentru $n = 10^9$ înseamnă vreo 30 de înmulțiri în loc de un miliard.