Ridicarea la putere în timp logaritmic
de Popa Sebastian
Enunț
Se dau trei numere naturale \(a\), \(b\) și \(\text{mod}\). Să se calculeze restul împărțirii lui \(a^b\) la \(\text{mod}\).
Observații
Desigur, această problemă se poate rezolva în timp liniar, efectuând \(b\) înmulțiri, însă acest procedeu este de cele mai multe ori prea lent. Pentru a rezolva această problemă eficient vom folosi următoarele proprietăți ale ridicării la putere:
- \(a^n \cdot a^m = a^{(n + m)}\)
- \({(a^n)}^m = a^{(n \cdot m)}\)
Rezolvare
Ne vom folosi de scrierea în baza \(2\) a exponentului. Astfel, pentru \(b = p_1 + p_2 + \ldots + p_t\) vom obține: \(a^b = a^{p_1 + p_2 + \ldots + p_t} = a^{p_1} \cdot a^{p_2} \cdot \ldots \cdot a^{p_t}\) unde \(p_i\) pentru \(1 ≤ i ≤ t\) sunt puteri distincte ale lui \(2\).
Valorile \(a^{p_i}\) pot fi calculate în complexitate logaritmică astfel: \(a^2 = {(a^1)}^2 , a^4 = {(a^2)}^2 , a^8 = {(a^4)}^2, \ldots, a^{(2^n)} = {(a^{(2^{n - 1})})}^2\).
Exemplu
\(\text{baza} = 3\), \(\text{exponent} = 5_{10} = 101_2\)
| \(i\) | \(a = \text{baza}^{(2^i)}\) | \(\text{exponent}\) | \(\text{rez}\) | \(\text{explicații}\) |
|---|---|---|---|---|
| \(0\) | \(3\) | \(101\) | \(3\) | bitul actual (cel mai din dreapta) este setat, deci inmultim rezultatul cu \(3\) |
| \(1\) | \(9\) | \(10\) | \(3\) | numarul cu care ar trebui sa inmultim devine \(9\) (\(3^2\)), dar ultimul bit nu este setat, deci nu modificam rezultatul |
| \(2\) | \(81\) | \(1\) | \(243\) | numarul cu care trebuie sa inmultim devine \(81\) (\(3^{(2^2)} = 92\)), ultimul bit este setat, deci inmultim rezultatul cu \(81\), acesta devenind \(243\) |
\(a = 2, b = 10_{10} = 1010_2\)
| \(a\) | \(b\) | \(rez\) |
|---|---|---|
| \(2\) | \(1010\) | \(1\) |
| \(4\) | \(101\) | \(4\) |
| \(16\) | \(10\) | \(4\) |
| \(256\) | \(1\) | \(1024\) |
Algoritmul va consta în scrierea în baza 2 a exponentului simultan cu efectuarea înmulțirilor necesare:
// rez = (a ^ b) % mod
rez = 1; // initializam rezultatul cu 1, acesta fiind rezultatul pt a^0, dar si elementul neutru pentru inmultire
a %= mod; //pentru a evita overflow
while (b) //cat timp b este diferit de 0, adică mai are biți setați, adică mai există termeni care trebuie puși la produs
{
if (b % 2 == 1) // dacă ultimul bit este setat înseamnă că termenul la care am ajuns trebuie adaugat la rezultat
rez = (1ll * rez * a) % mod; // rez = rez * (a^p[i])
a = (1ll * a * a) % mod; // p[i] = p[i - 1] ^ 2
b /= 2; // trecem la urmatorul bit; ex: 1010 devine 101 ; 1101 devine 110
}