Informatyka. Konkursy i algorytmy
szybkie potęgowanie
Do czego służy?
Algorytm szybkiego potęgowania służy do szybkiego obliczenia potęgi a^b. Pierwszy pomysł nasuwający się na myśl, to po prostu pomnożenie a przez siebie b razy. Jednak nie jest to optymalnie rozwiązanie... Będziemy bowiem potrzebowali aż b operacji. Jednak algorytm szybkiego potęgowania (quick potenging) zrobi to w dużo szybszym czasie! (log(b))
Algorytm
Zauważmy, że ab * ab = a2b (przy mnożeniu potęg o tej samej podstawie po prostu dodajemy wykładniki). Można by w takim razie naszą potęgę ab rozbić na dwie mniejsze, jeśli b jest parzyste. A co jak nie jest parzyste? Zauważmy, że a * ab - 1 to tyle samo co ab. (a = a1). Jeśli b jest nieparzyste, to znaczy że b - 1 jest parzyste, więc pozbyliśmy się problemu z nieparzystym wykładnikiem. Czyli nasz algorytm polega na rekurencji - jak dostajemy a i b, to jeśli b = 0 to zwracamy 1; Jeśli b jest parzyste to zwracamy ab / 2 * ab / 2(licząc potęgi naszą funkcją), w przeciwnym wypadku zwracamy ab - 1 * a;
Przykład
Zasymulujmy nasz algorytm szybkiego potęgowania dla przykładowej potęgi:
56
56 = 53 * 53
53 = 5 * 52
52 = 51 * 51
51 = 50 * 5
50 = 1
51 = 1 * 5 = 5
52 = 5 * 5 = 25
53 = 5 * 25 = 125
56 = 125 * 125 = 15625
Tutaj kończymy nasz algorytm, bo otrzymaliśmy wynik na nasze zapytanie.
Implementacja i złożoność
implementacja w c++:int pot(long long a, long long b){
if(b == 0){
return 1;
}
if(b % 2 == 0){
long long pom;
pom = pot(a, b / 2);
return (pom * pom) % mod;
}
else{
return a * pot(a, b - 1) % mod;
}
}
implementacja w python:
def pot(a, b):
if(b == 0):
return 1
if(b % 2 == 0):
pom = pot(a, b / 2)
return (pom * pom) % mod
else:
return a * pot(a, b - 1) % mod
złożoność: