De ce contează?
Vrei să urci 1000 de trepte. Le poți urca una câte una (1000 de pași) sau poți folosi un lift care, la fiecare apăsare, dublează etajul: 1, 2, 4, 8, 16... Ajungi mult mai sus cu foarte puține apăsări. Exponențierea rapidă e acest lift pentru puteri.
Problema cu metoda simplă
Ridicarea la putere prin înmulțiri repetate face n pași. Pentru n = 10⁹ — un miliard
de înmulțiri, prea lent. Trebuie ceva care crește exponentul mai repede.
Ideea: ridicarea la pătrat
Truc: în loc să adaugi câte un factor, dublează exponentul ridicând baza la pătrat.
a⁸ = (a⁴)² = ((a²)²)²
Dintr-un a² faci a⁴, apoi a⁸ — fiecare pas dublează exponentul. Iar orice exponent
se construiește din astfel de „bucăți" puteri ale lui 2, citind exponentul în binar.
13 în binar e 1101 = 8 + 4 + 1. Deci a¹³ = a⁸ · a⁴ · a¹. Parcurgem biții exponentului:
unde bitul e 1, includem puterea curentă a bazei în rezultat.
Algoritm pas cu pas: 3¹³
Pornește cu rezultat = 1, baza = 3, n = 13:
n | bit (n % 2) | acțiune | rezultat | baza devine |
|---|---|---|---|---|
| 13 | 1 | rezultat ·= baza | 3 | 9 |
| 6 | 0 | — | 3 | 81 |
| 3 | 1 | rezultat ·= baza | 243 | 6561 |
| 1 | 1 | rezultat ·= baza | 1.594.323 | — |
| 0 | — | stop | 1.594.323 | — |
Rezultat: 3¹³ = 1.594.323, în doar 4 pași în loc de 13.
Implementare C++
#include <iostream>
using namespace std;
long long putereRapida(long long baza, long long n, long long M) {
long long rezultat = 1;
baza %= M;
while (n > 0) {
if (n % 2 == 1) { // bitul curent e 1
rezultat = (rezultat * baza) % M;
}
baza = (baza * baza) % M; // ridicam baza la patrat
n /= 2; // trecem la bitul urmator
}
return rezultat;
}
int main() {
cout << putereRapida(3, 13, 1000000007) << "\n"; // 1594323
return 0;
}Cele trei mișcări la fiecare pas: (1) dacă n e impar, adaugă baza în rezultat; (2)
ridică baza la pătrat; (3) n /= 2. Modulo după fiecare înmulțire ține numerele mici.
Complexitate
| Metodă | Timp | Spațiu |
|---|---|---|
| înmulțiri repetate | O(n) | O(1) |
| exponențiere rapidă | O(log n) | O(1) |
Pentru n = 10⁹: ~30 de pași în loc de un miliard. E tehnica standard pentru aⁿ % M,
folosită și la inversul modular (mica teoremă a lui Fermat).
Vizualizare
Urmărește cum exponentul se înjumătățește pas cu pas, cum baza se ridică la pătrat și cum rezultatul „adună" doar bucățile unde bitul e 1:
Folosește ← → ca să mergi pas cu pas. Setează exponentul 13 și urmărește biții 1101:
vei vedea că rezultatul se actualizează exact la pașii unde bitul e 1.
Capcane reale la exponențierea rapidă:
- Overflow la
baza * baza: chiar cu modulo, dacăMe mare (~10⁹), produsul a două numere de ordinulMdepășeșteint. Lucrează înlong long. - Uiți modulo la un pas: dacă aplici
% Mdoar la rezultat, dar nu și la pătratul bazei, valoarea se sparge. Modulo după ambele înmulțiri. - Condiția bitului: verifici
n % 2 == 1(bit 1), nu== 0. Inversarea dă rezultat greșit. - Cazul
n = 0: bucla nu rulează, rezultatul rămâne 1 = a⁰ — corect, dar verifică să nu fi pus altrezultatinițial.
De reținut
- Dublezi exponentul prin ridicare la pătrat: a^(2k) = (a^k)² → O(log n) pași.
- Citește exponentul în binar: unde bitul e 1, înmulțești rezultatul cu baza curentă.
- Aplică modulo după fiecare înmulțire și lucrează în
long longca să eviți overflow-ul.