Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidă

Ridicarea la putere este o operație bineștiută, valoarea an fiind egală cu:

Algoritmul de determinare a ridicării la putere este una ușor de intuit, având complexitatea O(n) liniară:

int rasp = 1;
for(int i = 1; i <= n; i++) {
    rasp = rasp * a;
}
cout << a << "^" << n << " = " << rasp;

Mai precis, pentru a calcula operația an ne trebuie n operații de înmulțire… Cum putem optimiza algoritmul?

Cum putem ridica la putere într-un mod eficient

O metodă mai eficientă de a ridica la putere este ridicarea la putere în timp logaritmic, numită și exponențierea rapidă. Complexitatea acestui algoritm este O(log2 n). Această complexitate este incredibil de mică — spre exemplu, pentru a ridica un număr la puterea 1.000.000.000 (un miliard), facem aproximativ 30 de operații de înmulțire, în loc de un miliard cât ar fi luat cu metoda anterioară.

Cum funcționează exponențierea rapidă

Algoritmul de ridicare la putere în timp logaritmic se bazează pe următoarea observație:

Cu această observație, putem calcula 220 astfel:

• 220 = (210)2, deoarece n = 20 este par;
• 210 = (25)2, deoarece n = 10 este par;
• 25 = 2 * (22)2, deoarece n = 5 este impar;
• 22 = (21)2, deoarece n = 2 este par;
• 21 = 2 * (20)2, deoarece n = 1 este impar;
• 20 = 1.

Observăm că în loc să facem 20 de înmulțiri, efectuăm doar 6.

Implementare recursivă a exponențierii rapide

Implementarea recursivă folosește exact observația de mai sus:

int ridicare(int a, int n) {
    if(n == 0)
        return 1;

    if(n % 2 == 1) {
        int next = ridicare(a, (n - 1) / 2);
        return a * (next * next);
    } else {
        int next = ridicare(a, n / 2);
        return next * next;
    }
}

Implementarea iterativă a exponențierii rapide

Implementarea iterativă diferă un pic, însă se bazează pe aceeași idee. Să reprezentăm exponentul n ca sumă de puteri de 2. Spre exemplu, pentru n = 20, avem suma n = 4 + 16. Prin urmare, operația an = a20 = a(4 + 16) = a4 * a16 = (a1)0 * (a2)0 * (a4)1 * (a8)1 * (a16)1, unde exponenții de 0 și de 1 este reprezentarea binară a lui n = 20 (10100). Cu această idee, vom lua cifrele exponentului n în baza 2, de la ultima cifră către prima. Dacă cifra curentă este 1, atunci înmulțim răspunsul cu baza a. La fiecare pas, vom ridica baza a la pătrat.

Iată implementarea în C++:

int ridicare(int a, int n) {
    int rasp = 1;
    while(n > 0) {
        if(n % 2 == 1)
            rasp = rasp * a;
        a = a * a;
        n /= 2;
    }
    return rasp;
}

Probleme rezolvate

#2398 Moka (PbInfo)

Moca dorește să posteze pe Pbinfo a probleme de dificultate b. Durata postării celor a probleme de dificultate b este restul împărțirii lui ab la 1999999973. Ajutați-l pe Moca să calculeze durata postării celor a probleme de dificultate b. Pentru enunțul complet și testarea codului poți vizita această pagină.

Exemplu: Pentru a = 2 și b = 4, avem rezultatul 24 = 16.

Rezolvare: Deoarece b poate atinge valori mai mari de patru miliarde, rezolvarea problemei constă în aplicarea ridicării la putere în timp logaritmic. Observăm că rezultatul operației poate depăși cu mult orice tip de date (int, long long), astfel că după fiecare operație, trebuie să aplicăm restul împărțirii la 1999999973. Cum 1999999973 este un număr prim, rezultatul nu va atinge valoarea 0.

//Rezolvarea problemei #2398 Moka de pe PbInfo
//Explicații: https://infoas.ro
//Enunț: https://www.pbinfo.ro/probleme/2398/moka
#include <fstream>

using namespace std;

ifstream fin("moka.in");
ofstream fout("moka.out");

long long a, b;

long long ridicare(long long a, long long n) {
    long long rasp = 1;
    a = a % 1999999973; //În cazul în care baza depășește
        //Restul operațiilor sunt identice, doar că cu modulo 1999999973
    while(n > 0) {
        if(n % 2 == 1)
            rasp = rasp * a % 1999999973;
        a = a * a % 1999999973;
        n /= 2;
    }
    return rasp;
}

int main()
{
    fin >> a >> b;
    fout << ridicare(a, b);
    return 0;
}

Ridicare la putere in timp logaritmic: lgput (InfoArena)

Dându-se două numere naturale N și P, se cere să se calculeze restul împărțirii lui NP la 1999999973. Pentru enunțul complet al problemei și testarea soluțiilor vizitează această pagină.

Exemplu: Pentru numerele N = 2 și P = 5, soluția este 25 = 32.

Rezolvare: Observăm că problema este identică cu cea de dinainte (inclusiv operația modulo). Astfel, doar numele fișierelor se schimbă:

//Rezolvarea problemei lgput de pe InfoArena
//Explicații: https://infoas.ro
//Enunț: https://www.infoarena.ro/problema/lgput
#include <fstream>

using namespace std;

ifstream fin("lgput.in");
ofstream fout("lgput.out");

long long a, b;

long long ridicare(long long a, long long n) {
    long long rasp = 1;
    a = a % 1999999973; //În cazul în care baza depășește
        //Restul operațiilor sunt identice, doar că cu modulo 1999999973
    while(n > 0) {
        if(n % 2 == 1)
            rasp = rasp * a % 1999999973;
        a = a * a % 1999999973;
        n /= 2;
    }
    return rasp;
}

int main()
{
    fin >> a >> b;
    fout << ridicare(a, b);
    return 0;
}

Probleme propuse

#	Problemă	Dificultate
4.	Ridicare la putere in timp logaritmic	Medie (4 )
644.	Roboti	Medie (4 )
747.	Pandemia	Grea (8 )

Alte resurse sau bibliografie

• PbInfo: Exponențiere rapidă
• InfoArena: Ridicare la putere in timp logaritmic
• 100din100: Ridicarea la putere in timp logaritmic pentru olimpiada in C++