Algorytm szybkiego potęgowania

Algorytm szybkiego potęgowania – metoda pozwalająca na szybkie obliczenie potęgi o wykładniku naturalnym. Metoda ta wykorzystuje pośrednio dwójkową reprezentację wykładnika potęgi, a jej złożoność, wyrażona jako liczba wykonywanych mnożeń, wynosi ${\displaystyle \Theta (\log n),}$ gdzie ${\displaystyle n}$ oznacza wykładnik obliczanej potęgi.

Szybkie podnoszenie do potęgi w praktyce stosuje się do obliczania reszty z dzielenia potęgi przez ustaloną liczbę. Używa się go np. w algorytmach szyfru RSA.

Wprowadzenie[edytuj | edytuj kod]

Potęgowanie definiuje się za pomocą mnożenia

${\displaystyle {\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 ${\displaystyle k-1}$ mnożeń.

Dla dużego ${\displaystyle k}$ liczba wymaganych operacji może być bardzo duża. Jeśli ${\displaystyle k}$ ma ${\displaystyle j}$ cyfr, liczba operacji byłaby wykładnicza wobec ${\displaystyle j.}$

Algorytm[edytuj | edytuj kod]

Algorytm szybkiego potęgowania jest konsekwencją obserwacji, że aby obliczyć wartość ${\displaystyle a^{b}}$ wystarczy znać ${\displaystyle a^{\lfloor b/2\rfloor }}$ (${\displaystyle \lfloor \cdot \rfloor }$ oznacza część całkowitą), a następnie wykonać jedno lub dwa mnożenia. Np. aby obliczyć ${\displaystyle 5^{175}}$ wystarczy znać wartość ${\displaystyle x=5^{87},}$ a następnie policzyć ${\displaystyle y=x^{2}=5^{174}}$ i wynik wynosi ${\displaystyle y\cdot 5.}$ W ten sposób, aby wykonać jeden krok algorytmu, czyli przejść od ${\displaystyle 5^{87}}$ do ${\displaystyle 5^{175},}$ wystarczy wykonać 2 mnożenia zamiast 88, jak wynikałoby to z przytoczonej wyżej definicji.

Pseudokod[edytuj | edytuj kod]

Z powyższych obserwacji można uzyskać rekurencyjną funkcję szybkiego obliczania wartości ${\displaystyle 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 

Po optymalizacji można otrzymać następującą postać:

funkcja potęga(x, n)     jeżeli n = 0         zwróć 1     jeżeli n jest nieparzysta         zwróć x · (potęga(x, (n - 1)/2))2     zwróć (potęga(x, n/2))2 

Ten sam algorytm w wersji iteracyjnej wygląda następująco:

w:= 1 dla a = m do 1   // m - ilość miejsc binarnych liczby n     c = a-ta cyfra binarna liczby n     jeżeli c = 0        w:= w · w     jeżeli c = 1        w:= w · w · x 

po zakończeniu powyższego algorytmu w zmiennej ${\displaystyle w}$ jest pamiętana ${\displaystyle n}$-ta potęga liczby ${\displaystyle x.}$

Linki zewnętrzne[edytuj | edytuj kod]

• Szybkie potęgowanie – wykład, kanał Olimpiady Informatycznej Juniorów (OIJ) na YouTube, 14 listopada 2014 [dostęp 2023-11-24].