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