De ce contează?
Vrei 1024 de copii ale unei foi. Ai putea apăsa „copiază” de 1024 de ori la rând — sau copiezi foaia o dată (2 foi), apoi copiezi teancul (4), apoi iar (8), 16, 32... În doar 10 apăsări ai 1024 de foi. Asta e diferența: când dublezi în loc să aduni câte unu, ajungi departe în pași foarte puțini. Exact așa ridicăm un număr la o putere uriașă — fără să facem un miliard de înmulțiri.
Intuiția
Lecția anterioară a calculat a^n înmulțind a cu el însuși de n ori. Dar
observă că o putere se desface în jumătăți: a^10 = a^5 * a^5 = (a^5)^2. Pe
a^5 îl calculezi o singură dată și îl ridici la pătrat. Cu fiecare pătrat,
exponentul se înjumătățește — din 10 ajungi la vreo 4 pași, adică la log n
pași în loc de n.
Ideea centrală, scrisă o dată: a^n = (a^(n/2))^2. Nu aduni exponentul câte
unu — îl înjumătățești la fiecare pas, ridicând baza la pătrat. Înjumătățirea
repetată a lui n e chiar motivul pentru care ajungi în log n pași.