Exponențiere rapidă

Ridicarea la putere este o operație binecunoscută, formulă uzuală fiind: $$A^n=\prod _{i=1}^{n}A=\underset{\text{de }n\text{ ori}}{\underbrace{A\times A\times \dots \times A}}$$

Un algoritm care implementează această metodă va avea complexitate liniară, $O(n)$:

int Putere(int A , int n)
{
    int P = 1 ;
    for(int i = 1 ; i <= n ; i ++)
        P = P * A;
    return P;
}

Descriere

O metodă mai bună este cea numită exponențierea rapidă , sau ridicarea la putere în timp logaritmic, complexitatea sa fiind $O({\log }_{2}n)$. Ea se bazează pe următoarea formulă:

$$A^n=\{\begin{array}{ll}1& \text{, dacă }n=0\\ A\cdot A^{n-1}& \text{, dacă }n\text{ – impar}\\ {\left(A^{\frac{n}{2}}\right)}^2& \text{, dacă }n\text{ – par}\end{array}$$

Exemplu

Să calculăm $2^{25}$:

• $2^{25}=2\cdot 2^{24}$, deoarece 25 este impar
• $2^{24}={(2^{12})}^2$, deoarece 24 este par
• $2^{12}={(2^6)}^2$, deoarece 12 este par
• $2^6={(2^3)}^2$, deoarece 6 este par
• $2^3=2\cdot 2^2$, deoarece 3 este impar
• $2^2={(2^1)}^2$, deoarece 2 este par
• $2^1=2\cdot 2^0$, deoarece 1 este impar
• $2^0=1$

Atunci în ordine inversă:

• $2^1=2\cdot 1=2$
• $2^2=2^2=4$
• $2^3=2\cdot 4=8$
• $2^6=8^2=64$
• $2^{12}={64}^2=4096$
• $2^{24}={4096}^2=16777216$
• $2^{25}=2\cdot 16777216=33554432$

Constatăm că numărul înmulțirilor efectuate este mult mai mic decât în cazul primei metode.

Implementare recursivă

Implementarea recursivă este directă:

int Putere(int A , int n)
{
    if(n == 0)
        return 1;
    if(n % 2 == 1)
        return A * Putere(A , n - 1);
    int P = Putere(A , n / 2);
    return P * P;
}

Implementare iterativă

Să considerăm $A^{25}$. Să-l scriem pe $25$ ca sumă de puteri ale lui $2$ (orice număr natural poate fi scris ca sumă de puteri ale lui $2$ într-un singur mod): $25=1+8+16$.

Atunci $A^{25}=A^{1+8+16}=A^1\cdot A^8\cdot A^{16}=\underset{=A^1}{\underbrace{{(A^1)}^1}}\cdot \underset{=1}{\underbrace{{(A^2)}^0}}\cdot \underset{=1}{\underbrace{{(A^4)}^0}}\cdot \underset{=A^8}{\underbrace{{(A^8)}^1}}\cdot \underset{=A^{16}}{\underbrace{{(A^{16})}^1}}$. Observăm că exponenții $0$ și $1$ sunt cifrele reprezentării în baza $2$ a lui $25$.

Se figurează următoarea idee, pentru a determina An:

• vom determina un produs P, format din factori de forma A1, A2, A4, A8, …
• determinăm cifrele reprezentării în baza 2 a lui n, începând cu cea mai nesemnificativă:
  • dacă cifra curentă este 1, înmulțim pe A la P, P = P * A;
  • înmulțim pe A cu el însuși, A = A * A;, obținând următoarea putere din șirul de mai sus

Implementare C++:

int Putere(int A , int n)
{
    int P = 1;
    while(n)
    {
        if(n % 2 == 1)
            P = P * A;
        A = A * A;
        n /= 2;
    }
    return P;
}

altă variantă, care folosește operațiile pe biți:

int Putere(int A , int n)
{
    int P = 1;
    for(int k = 1 ; k <= n ; k <<= 1)
    {
        if((n & k))
            P *= A;
        A = A * A;
    }
    return P;
}

Observații

• ridicarea la putere rapidă poate fi folosită și pentru:
  • operații modulo (determinarea restului împărțirii rezultatului la o valoare dată)
  • numere mari
  • ridicarea la putere a matricelor
  • ridicarea la putere a polinoamelor