Algorytm szybkiego potęgowania (ang. Exponentiation by Squaring) pozwala na obliczenie wartości potęgi w czasie znacznie krótszym niż tradycyjne podejście, które polega na mnożeniu liczby przez siebie n razy. Standardowa metoda, czyli wielokrotne mnożenie, działa w czasie O(n), natomiast szybkie potęgowanie obniża złożoność czasową do O(log n).
Kluczowa idea
Algorytm opiera się na podziale problemu i wykorzystaniu faktu, że:
Dla liczby parzystej n, potęgę można przekształcić w:
an =(an/2 )2
co oznacza, że wystarczy policzyć a podniesione do połowy potęgi, a wynik podnieść do kwadratu.
Dla liczby nieparzystej n, potęgowanie możemy uprościć w następujący sposób:
a n =a⋅an−1
gdzie a^{n-1} jest liczbą parzystą, którą można dalej przekształcić zgodnie z zasadą powyżej.
Algorytm działa rekurencyjnie lub iteracyjnie, dzieląc problem na mniejsze części aż do osiągnięcia podstawy, którą jest n = 0 (bo każda liczba podniesiona do potęgi 0 równa się 1). Dla każdej kolejnej połowy problemu wynik jest odpowiednio przekształcany i mnożony.
Zdefiniuj potęgę:
Jeśli n = 0, wynik to 1 (bo każda liczba podniesiona do potęgi 0 równa się 1).
Jeśli n jest parzyste, oblicz a^{n/2}, a następnie podnieś ten wynik do kwadratu.
Jeśli n jest nieparzyste, oblicz a^{n-1}, a następnie pomnóż przez a.
Przykład działania
Rozważmy obliczenie 35.
Krok 1: 5 jest nieparzyste, więc:
35 =3⋅34
Krok 2: 4 jest parzyste, więc:
34 =(32 )2
Krok 3: Obliczamy 32=9 i podnosimy do kwadratu:
3 4 =92 =81
Krok 4: Wracamy do 35:
35 =3⋅81= 243
Dzięki tej metodzie zamiast wykonywać 5 mnożeń, wykonujemy tylko 3 mnożenia.
Algorytm można zapisać w formie iteracyjnej, gdzie potęgę oblicza się w pętli, bez użycia rekurencji. Używamy zmiennej wynik, która jest stopniowo mnożona przez bazę, jeśli n jest nieparzyste, a następnie kwadrat bazy, gdy n jest parzyste. Wartość n dzielimy przez 2 przy każdym kroku.
Zalety algorytmu:
Zastosowanie w obliczeniach na dużych liczbach (np. kryptografia).
Szybkość, szczególnie w porównaniu z tradycyjnym podejściem mnożenia.
Szybkie potęgowanie jest przydatne tam, gdzie wymagane jest szybkie liczenie potęg w dużych systemach numerycznych, np. w kryptografii, grafice komputerowej, czy algorytmach numerycznych.
Iteracyjne potęgowanie działa w pętli, dopóki wykładnik n jest większy od 0. W każdym kroku wykonuje kwadratowanie bazy, dzieli wykładnik przez 2, a jeśli wykładnik jest nieparzysty, mnoży wynik przez bazę.
Wejście:
a - baza (liczba, którą podnosimy do potęgi)
n - wykładnik (potęga)
Wyjście:
wynik - wynik potęgowania (a^n)
Zmienne pomocnicze:
wynik - zmienna przechowująca wynik potęgowania
a - zmienna baza, która będzie modyfikowana w czasie pętli
n - zmienna wykładnik, która będzie zmniejszana o połowę
Lista kroków:
K1: wynik ← 1 (Inicjalizacja wyniku jako 1)
K2: Dopóki n > 0
wykonuj kroki od K3 do K6
K3: Jeśli n % 2 = 1
to wynik ← wynik * a (Jeśli wykładnik nieparzysty, pomnóż wynik przez bazę)
K4: a ← a * a (Kwadratowanie bazy)
K5: n ← n / 2 (Dzielimy wykładnik przez 2)
K6: Zakończ pętlę
K7: Zwróć wynik (Zwracamy końcowy wynik)Wynik działania programu:
Podaj baze (a): 3
Podaj wykladnik (n): 5
3^5 = 243Rekurencyjne potęgowanie używa podziału problemu na mniejsze części: jeśli wykładnik jest parzysty, problem dzieli się na połowę, jeśli jest nieparzysty, zmniejsza wykładnik o 1 i mnoży przez bazę.
Wejście:
a - baza (liczba, którą podnosimy do potęgi)
n - wykładnik (potęga)
Wyjście:
wynik - wynik potęgowania (a^n)
Lista kroków:
K1: Jeśli n = 0
zwróć 1 (Każda liczba do potęgi 0 to 1)
K2: Jeśli n % 2 = 0
to wynik ← SzybkiePotRekurencyjne(a * a, n / 2) (Dzielimy wykładnik przez 2, kwadratujemy bazę)
K3: Jeśli n % 2 = 1
to wynik ← a * SzybkiePotRekurencyjne(a, n - 1) (Jeśli wykładnik nieparzysty, pomnóż przez bazę i zmniejsz wykładnik o 1)
K4: Zwróć wynik (Zwracamy końcowy wynik)Wynik działania programu:
Podaj baze (a): 3
Podaj wykladnik (n): 5
3^5 = 243