Exponențiere rapidă

Ridicarea la putere este o operație binecunoscută, formulă uzuală fiind:

$$A^n = \prod_{i=1}^n {A} = \underbrace{A \times A \times … \times A }_{\text{de } n \text{ ori}}$$

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{cases} 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{cases}$$

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} = \underbrace{{(A^1)}^1}_{=A^1} \cdot \underbrace{{(A^2)}^0}_{=1} \cdot \underbrace{{(A^4)}^0}_{=1} \cdot \underbrace{{(A^8)}^1}_{=A^8} \cdot \underbrace{{(A^{16})}^1}_{=A^{16}}$. 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