Szybkie podnoszenie aż do potęgi w praktyce stosuje się aż do liczenia reszty spośród dzielenia potęgi dzięki ustaloną liczbę. Używa się go np. w algorytmach szyfru RSA.
Wprowadzenie
Potęgowanie definiuje się za pomocą mnożenia
begin{matrix} x^k = x cdot x^{k-1} = & underbrace{x cdot x cdot x cdot ldots cdot x } & {}^k end{matrix},
co daje łącznie k-1 mnożeń.
Dla dużego k liczba wymaganych operacji może być bardzo duża. Jeśli k ma j cyfr, liczba operacji byłaby wykładnicza wobec j.
Algorytm
Algorytm szybkiego potęgowania jest konsekwencją obserwacji, że aby obliczyć wartość a^b wystarczy znać a^{lfloor b/2rfloor} (lfloorcdotrfloor oznacza część całkowitą), a następnie wykonać jedno lub dwa mnożenia. Np. aby obliczyć 5^{175} wystarczy znać wartość x=5^{87}, a następnie policzyć y=x^2=5^{174} i wynik wynosi =ycdot 5. W ten sposób aby przejść od 5^{87} do 5^{175} wystarczy wykonać 2 mnożenia zamiast 88, jak wynikałoby to z przytoczonej wyżej definicji.
Pseudokod
Dostajemy z powyższej obserwacji rekurencyjną funkcję szybkiego obliczania wartości x^n.
funkcja potęga(x, n)
jeżeli n = 0
zwróć 1
jeżeli n jest nieparzysta
zwróć x · potęga(x, n – 1)
w przeciwnym przypadku
a = potęga(x, n/2)
zwróć a2
Ten sam algorytm w wersji iteracyjnej wygląda następują
- w:=1
- dla wszystkich cyfr rozwinięcia dwójkowego liczby n zaczynając od najbardziej znacząc
jeśli cyfra jest zerem to w:=w*w
jeśli cyfra jest jedynką to w:=w*w*x
po zakończeniu powyższego algorytmu w zmiennej w jest pamiętana n-ta potęga liczby x.
creativewaterfeatures 