.png)
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\)
\(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.