Szybkie potęgowanie

Metoda obliczania wartości potęgi $x^n$.
Naiwne obliczanie $x^n$ polega na wykonaniu aż $n-1$ mnożeń. Jednak można tę liczbę operacji skrócić. Wystarczy, że będziemy podstawę potęgi podnosić do kwadratu jak najdłużej, gdy wartość wykładnika przekroczy $n$, to wykorzystujemy wcześniej obliczone wartości.

Przykład

Obliczyć $2^{11}$
$2\cdot 2 = 2^{2} = 4$
$(2^{2})^{2} = 2^{4} = 16$
$(2^{4})^2 = 2^8 = 256$
Kolejne podniesienie do kwadratu przekroczy 10, więc nie podnosimy dalej, tylko mnożymy przez wcześniej obliczone potęgi.
$2^{11}=2^{8}\cdot 2^{2}\cdot 2 = 256 \cdot 4 \cdot 2 = 2048$
Liczba mnożeń w tym przypadku wynosi $5$, zamiast $10$.
Rząd wielkości liczby operacji jest potęgą dwójki
$2^{k} = n$
$n = \lfloor \log_2(n)\rfloor$
Jest to jest złożoność logarytmiczna, co w porównaniu do poprzedniej naiwnej metody o złożoności liniowej jest szokującym wynikiem. Wystarczy porównać wykresy funkcji liniowej i logarytmicznej, żeby zauważyć, że funkcja logarytmiczna rośnie tym wolniej im większe $n$ i dużo wolniej od funkcji liniowej, która rośnie proporcjonalnie do n.
Jak nauczyć tej metody komputer?
Obliczamy metodą szybkiego potęgowania, tak jak poprzednio: $x^{11} = ((x^2)^2)^2 \cdot x^{2}\cdot x^{1}= x^{8+2+1} = x^{2^{3}+2^{1}+2^{0}} = x^{(1011)_{2}}$
Algorytm szybkiego potęgowania sprowadza się do przedstawienia wykładnika potęgi do postaci binarnej i wykonaniu odpowiednich mnożeń.
Postępujemy według pseudokodu:

Ustawmy wynik = 1:
    jeśli kolejny bit jest równy 0
(licząc od prawej), podstawę nadpisujemy jej kwadratem
jeśli kolejny bit jest równy 1
     wynik przemnażamy przez aktualną wartość podstawy, a podstawę nadpisujemy jej kwadratem.
 Czynności powtarzamy do wyczerpania bitów w liczbie.

Znając efektywny algorytm zapisu wykładnika potęgi w postaci binarnej i stosując powyższy algorytm łatwo zaprogramujemy metodę szybkiego potęgowania w dowolnym języku programowania.

Uwaga

Zapamiętaj, że szybkie potęgowanie polega na ciągłym podnoszeniu potęgi do kwadratu i ewentualnym przemnożeniu wyniku przez obliczone już wartości, natomiast zapis binarny wykładnika służy tylko do sprytnego i efektywnego zapisu tego algorytmu.

Ćwiczenie

Obliczyć metodą szybkiego potęgowania $(\sqrt{2} – 1)^{9}$