Algorytm szybkiego potęgowania

Algorytm szybkiego potęgowania

Rodzaj	Potęgowanie
Złożoność
Czasowa	$\Theta (\log n)$ $n$ – wykładnik

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 $\Theta (\log n),$ gdzie $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

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/2\rfloor }$ ($\lfloor \cdot \rfloor$ 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 $y\cdot 5.$ W ten sposób, aby wykonać jeden krok algorytmu, czyli przejść od $5^{87}$ do $5^{175},$ wystarczy wykonać 2 mnożenia zamiast 88, jak wynikałoby to z przytoczonej wyżej definicji.

Pseudokod

Z powyższych obserwacji można uzyskać 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

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 $w$ jest pamiętana $n$-ta potęga liczby $x.$

Linki zewnętrzne

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