Algorytm szybkiego potęgowania

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
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 liczenia 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

\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[edytuj | edytuj kod]

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 przejść od 5^{87} do 5^{175} wystarczy wykonać 2 mnożenia zamiast 88, jak wynikałoby to z przytoczonej wyżej definicji.

Pseudokod[edytuj | edytuj kod]

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ąco:

  1. w:=1
  2. dla wszystkich cyfr rozwinięcia dwójkowego liczby n zaczynając od najbardziej znaczącej:
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.