Exponențiere rapidă

Exponențierea rapidă calculează $a^n$ pentru exponent întreg nenegativ prin înjumătățirea repetată a exponentului. Dacă $n$ este par, $a^n=(a^2{)}^{n/2}$; dacă este impar, păstrăm încă un factor $a$. Astfel, $3^5$ se obține din factori corespunzători cifrelor 1 din scrierea lui 5 în baza 2 ($5=101_2$): $3^5=3^4\cdot 3^1$, nu prin cinci înmulțiri consecutive obligatorii.

Calculul lui $a^n$ prin $n-1$ înmulțiri consecutive necesită un număr de pași proporțional cu $n$. Exponențierea rapidă se bazează pe scrierea exponentului în baza 2. Dacă $n=n_k\dots n_1{n}_0$ sunt cifrele lui binare, atunci $a^n={\prod }_{i:n_i=1}{a}^{2^i}$. Puterile $a^{2^i}$ se obțin prin pătrățiri succesive, iar la fiecare pas se verifică ultima cifră binară a exponentului, adică exp % 2. Ciclul are $[{\log }_{2}n]+1$ iterații: pentru $n=10^{18}$ sunt doar 60.

Metoda se potrivește calculului cu numere mari și testelor pe șiruri de puteri. Pentru $2^{30}$ se fac 5 iterații în loc de 29 de înmulțiri.

Invarianta ciclului este: $\text{rezultat}\cdot {\text{baza}}^{\text{exp}}$ este egal cu $a^n$ la începutul fiecărei iterații. La început rezultat=1, baza=a, exp=n. Dacă exp este impar, factorul baza trece în rezultat; apoi baza se pătrățește și exp se înjumătățește (împărțire întreagă). Când exp devine 0, rezultat este $a^n$.

Exemplul 1 — $3^5$. Exponentul $5=101_2$ are ultima cifră 1, apoi 0, apoi 1.

1. exp=5 (impar): rezultat=1·3=3; baza=3²=9; exp=2.
2. exp=2 (par): rezultat rămâne 3; baza=9²=81; exp=1.
3. exp=1 (impar): rezultat=3·81=243; baza=81²=6561; exp=0.

Ciclul se oprește cu rezultat=243, adică $3^5=3^1\cdot 3^4$. S-au făcut trei iterații în loc de patru înmulțiri consecutive.

baza = 3
exp = 5
rezultat = 1
while exp > 0:
    if exp % 2 == 1:
        rezultat *= baza
    baza *= baza
    exp //= 2
print(rezultat)

Pentru $n=10=1010_2$ ciclul face patru iterații și numai două înmulțiri ale rezultatului, la cifrele 1 de pe pozițiile 1 și 3: $a^{10}=a^2\cdot a^8$. Pentru $a^{40}$ înmulțirile consecutive cer 39 de pași, pe când $40=101000_2$ cere șase iterații și numai două înmulțiri ale rezultatului, cu $a^8$ și cu $a^{32}$. Aceeași idee se scrie și recursiv: $a^n=(a^{n/2}{)}^2$ pentru $n$ par, $a^n=a\cdot a^{n-1}$ pentru $n$ impar și $a^0=1$; ambele variante au același număr de pași, dar cea iterativă nu folosește stiva de apeluri.

Exemplul 2 — puterea modulo $m$. La exponenți mari rezultatul depășește orice tip întreg, iar problemele cer restul. Se aplică restul după fiecare înmulțire, pentru că $(x\cdot y)\mathrm{mod}m=((x\mathrm{mod}m)\cdot (y\mathrm{mod}m))\mathrm{mod}m$. Pentru $3^{13}\mathrm{mod}100$, exponentul $13=1101_2$ are trei cifre 1:

#include <iostream>
using namespace std;
int main() {
    long long baza = 3, exp = 13, mod = 100, rezultat = 1;
    while (exp > 0) {
        if (exp % 2 == 1)
            rezultat = rezultat * baza % mod;
        baza = baza * baza % mod;
        exp /= 2;
    }
    cout << rezultat;
    return 0;
}

Programul afișează 23, deoarece $3^{13}=1594323$ și restul împărțirii la 100 este 23. Valorile lui baza modulo 100 sunt 3, 9, 81, 61, iar factorii aleși sunt 3, 81 și 61 (exponenții 1, 4 și 8 ai lui 3 în $3^{13}$): $3\cdot 81=243\to 43$ și $43\cdot 61=2623\to 23$. Se folosește long long pentru ca produsul a două resturi mai mici decât $m$ să încapă în tip.

Exemplul 3 — $7^{12}$ și cazul $n=0$. Exponentul $12=1100_2$ are două cifre 0 la sfârșit, deci primele două iterații nu schimbă rezultat: la exp=12 și exp=6 baza devine 49, apoi 2401. La exp=3 (impar) rezultat=2401, iar baza devine $2401^2=5764801$. La exp=1 rezultatul este $2401\cdot 5764801=13841287201$, adică $7^4\cdot 7^8=7^{12}$. Valoarea depășește 2147483647, deci variabilele sunt long long. Pentru $n=0$ ciclul nu se execută și rămâne rezultat=1, valoare corectă pentru $a^0$.

Atenție la ultima pătrățire. În ultima iterație baza se pătrățește chiar dacă valoarea nu mai este folosită; pentru $7^{12}$ ea ajunge la 33 232 930 569 601, încă în long long. La baze mari fără modul, această pătrățire inutilă poate depăși tipul înaintea rezultatului, deci se verifică limitele din enunț.

Greșeli frecvente

• Greșit: la exponent par se mai înmulțește rezultatul cu baza.
  Corect: acel factor se adaugă numai când exponentul este impar.
• Greșit: baza *= baza este o adunare.
  Corect: pătrățește baza.
• Greșit: pentru exponentul zero rezultatul este zero.
  Corect: $a^0=1$ pentru $a\ne 0$.

Înainte și după