Szybkie potęgowanie – Python, C++ i Java

Szybkie potęgowanie to jedna z podstawowych technik wykorzystywanych w algorytmice, szczególnie tam, gdzie konieczne jest operowanie na bardzo dużych liczbach. Klasyczne mnożenie krok po kroku staje się w takich przypadkach zbyt wolne, dlatego stosuje się metody pozwalające znacząco przyspieszyć obliczenia.

Co to szybkie potęgowanie?

Szybkie potęgowanie to technika stosowana w informatyce i matematyce obliczeniowej, która pozwala znacznie skrócić czas obliczania dużych potęg liczby. Zamiast wykonywać kolejne mnożenia wprost, metoda ta wykorzystuje rozkład wykładnika i zasadę potęgowania przez podnoszenie do kwadratu. Dzięki temu złożoność obliczeń spada z liniowej do logarytmicznej, co ma ogromne znaczenie zwłaszcza w kryptografii i algorytmach numerycznych.

W przypadku szybkiego potęgowanie w ramach informatyki, mowa o algorytmie szybkiego potęgowania, jednak w zagranicznych serwisach, można trafić na nazwy takie jak potęgowanie przez podnoszenie do kwadratu (exponentiating by squaring) lub potegowanie binarne (binary exponentiation).

Gdy w szkole wprowadzane jest potęgowanie definiowane jest jako liczba przemnożona przez siebie tyle razy ile wynosi wartość wykładnika. Gdybyśmy na podstawie tej definicji mieli napisać algorytm podnoszący liczbę do potęgi prawdopodobnie składałby się on z pętli i wykonywał k-1 mnożeń, gdzie k to wartość wykładnika. Jest to złożoność liniowa – jednak istnieje tutaj miejsce na optymalizację.

Wykorzystamy tu zależność: gdy chcemy policzyć xn możemy obliczyć (xn/2)2 i na pierwszy rzut oka nic to nie zmienia, ale musimy zdać sobie sprawę, że liczymy xn/2 tylko raz co znacznie przyspiesza liczenie.

Metoda klasyczna – liczba mnożeń

28=2*2*2*2*2*2*2*2*2=256

(liczba mnożeń: 7)

Metoda szybka – liczba mnożeń

28=24*24

24=22*22

22=2*2

(liczba mnożeń: 3)

Jak widać liczba operacji mnożenia jest ponad 2 razy mniejsza. Tylko co jeśli napotkamy nieparzysty wykładnik np. x15? Można wtedy po prostu zapisać działanie w postaci x14*x.

x15=x14*x

x14=x7*x7

x7=x6*x

x6=x3

x3=x2*x

x2=x

(liczba mnożeń: 6 – w wersji klasycznej: 14)

Algorytm szybkiego potęgowanie – Implementacja

Szybkie potęgowanie rekurencyjnie – Schemat blokowy i pseudokod

Szybkie potęgowanie w formie rekurencyjnej korzysta z zasady dzielenia problemu na mniejsze podproblemy. Funkcja wywołuje samą siebie z wykładnikiem podzielonym na dwa, aż do osiągnięcia przypadku bazowego, czyli n = 0.

Opis szybkiego potęgowania rekurencyjnie – Pseudokod

• 1 linia – definicja funkcji przyjmującej podstawę x i wykładnik n.
• 2 linia – sprawdzenie, czy wykładnik n jest równy zero.
• 3 linia – jeśli tak, zwracamy 1, ponieważ każda liczba do potęgi 0 daje 1.
• 4 linia – sprawdzenie, czy wykładnik n jest nieparzysty (n mod 2 = 1).
• 5 linia – jeśli n jest nieparzyste, wywołujemy funkcję dla n – 1 i mnożymy wynik przez x.
• 6 linia – wywołanie funkcji dla n div 2 (czyli n podzielone przez 2, bez reszty) i zapisanie tego wyniku w zmiennej „obliczona”.
• 7 linia – zwrócenie wartości obliczona pomnożonej przez obliczona, czyli podniesienie jej do kwadratu.

Szybkie potęgowanie rekurencyjnie – Python, C++ i Java

Szybkie potęgowanie iteracyjnie – Schemat blokowy i pseudokod

Szybkie potęgowanie w formie iteracyjnej opiera się na wykorzystaniu pętli, w której wykładnik jest stopniowo zmniejszany poprzez dzielenie przez dwa. Przy każdym kroku sprawdzamy, czy aktualny wykładnik jest nieparzysty, a jeśli tak, to wynik mnożymy przez podstawę.

Opis szybkiego potęgowania iteracyjnie – Pseudokod

• 1 linia – definicja funkcji potega_iter przyjmującej podstawę x i wykładnik n.
• 2 linia – inicjalizacja zmiennej wynik wartością 1, która będzie akumulować końcowy rezultat.
• 3 linia – rozpoczęcie pętli dopóki n > 0, która powtarza kroki algorytmu aż wykładnik zostanie zredukowany do zera.
• 4 linia – sprawdzenie warunku jeżeli n mod 2 == 1, czyli czy bieżący wykładnik jest nieparzysty.
• 5 linia – gdy wykładnik jest nieparzysty, aktualizujemy akumulator: wynik ← x * wynik, aby uwzględnić bieżącą potęgę.
• 6 linia – podnosimy do kwadratu podstawę: x ← x * x, przygotowując ją do następnego kroku dzielenia wykładnika przez dwa.
• 7 linia – zmniejszamy wykładnik przez podzielenie bez reszty: n ← n div 2, co przesuwa analizę w kierunku bitów wyższych.
• 8 linia – po zakończeniu pętli zwracamy wynik, który zawiera wartość x podniesioną do potęgi n.

Szybkie potęgowanie iteracyjnie – Python, C++ i Java

Działa ona jednak trochę inaczej. W tym przypadku x zawsze przechowuje parzyste potęgi, a gdy napotkamy nieparzysta potęgę mnożymy wynik * x jako że mnożenie jest przemienne nie jest to problem. Dla każdej liczby oprócz zera w ostatniej iteracji n = 1, wynik zostanie na koniec przemnożony przez x w odpowiedniej potędze. Dla n = 0 pętla się nie wykona i po prostu otrzymamy 1.

Najczęściej zadawane pytania o szybkie potęgowanie