Ridicare la putere în timp logaritmic

De ce contează?

Ca să calculezi 2³², nu înmulțești 2 de 32 de ori. Ridici la pătrat: 2², apoi (2²)² = 2⁴, apoi 2⁸, 2¹⁶, 2³² — doar 5 pași. Fiecare pătrat dublează exponentul, așa că ajungi sus în pași logaritmici, nu liniari.

Problema

Vrei a^n pentru n mare (până la un miliard sau mai mult). Metoda naivă înmulțește baza de n ori — O(n), prea lent. Exponentierea rapidă o face în O(log n).

Ideea: pătrate repetate

Observația cheie:

a^(2k)   = (a^k)²        (exponent par)
a^(2k+1) = a · (a^k)²    (exponent impar)

La fiecare pas înjumătățești exponentul. Din n ajungi la 0 în ~log₂(n) pași.

Observația-cheie

De ce e atât de eficient: înjumătățind exponentul de fiecare dată, faci ~30 de înmulțiri pentru n ≈ 10⁹, nu un miliard. Aceeași idee de „a ataca problema prin jumătăți" ca la căutarea binară.

Varianta recursivă

long long putere(long long a, long long n) {
    if (n == 0) return 1;          // caz de baza: a^0 = 1
    long long jum = putere(a, n / 2);
    long long p = jum * jum;        // (a^(n/2))^2
    if (n % 2 == 1) p = p * a;      // exponent impar: inca un a
    return p;
}

Calculezi o singură dată a^(n/2), apoi îl ridici la pătrat — aici e câștigul față de naiv.

Varianta iterativă (pe biți)

Parcurgi exponentul bit cu bit. Ții o baza care se ridică la pătrat la fiecare pas; când bitul curent e 1, înmulțești rezultatul cu baza:

long long putere(long long a, long long n) {
    long long rez = 1;
    while (n > 0) {
        if (n & 1) rez = rez * a;   // bit 1 -> contribuie
        a = a * a;                  // ridic baza la patrat
        n >>= 1;                    // urmatorul bit
    }
    return rez;
}

Exemplu pas cu pas

3^13. În binar, 13 = 1101.

n=13 (1101): bit 1 -> rez=3;      a=9    (3^2)
n=6  (110):  bit 0 -> rez=3;      a=81   (3^4)
n=3  (11):   bit 1 -> rez=243;    a=6561 (3^8)
n=1  (1):    bit 1 -> rez=1594323; a=...
n=0: stop

Rezultat: 3^13 = 1594323. ✓ Doar 4 pași în loc de 13 înmulțiri.

Complexitate

Metodă	Înmulțiri	Timp
naivă	n	O(n)
exponentiere rapidă	~log₂(n)	O(log n)

Vizualizare

Urmărește cum exponentul n se înjumătățește pas cu pas și cum baza se ridică la pătrat — a^(2k) = (a^k)² — adunând în rezultat doar puterile pentru care bitul curent e 1:

Indiciu

Folosește ← și → pentru a avansa. Observă cum fiecare pas dublează exponentul acumulat — aceeași idee ca la puterea unui număr.

Greșeli frecvente

Capcane la exponentierea rapidă:

Overflow: a * a crește exploziv. Pentru puteri mari fără modulo, rezultatul depășește long long repede. De obicei se cere rezultatul modulo un număr prim (vezi lecția următoare).
Caz de bază lipsă: fără n == 0 -> 1, recursivitatea nu se oprește.
Confuzi n / 2 cu n % 2: înjumătățirea e n / 2; paritatea (bit impar) se verifică cu n % 2 sau n & 1.
Recalculezi a^(n/2) de două ori: dacă scrii putere(a,n/2) * putere(a,n/2), pierzi tot câștigul — devine din nou O(n). Salvează rezultatul într-o variabilă.

Recapitulare

Exponentierea rapidă folosește a^(2k) = (a^k)², înjumătățind exponentul la fiecare pas → O(log n) înmulțiri.
Varianta iterativă parcurge exponentul pe biți: ridici baza la pătrat mereu, înmulțești rezultatul când bitul e 1.
Salvează a^(n/2) o singură dată (recursiv) și atenție la overflow — de regulă se lucrează modulo.