Algorytm szybkiego potęgowania


Algorytm szybkiego potęgowania w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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 Θ ( log n ) , {\displaystyle \Theta (\log n),} gdzie n {\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 kod

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

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

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

Algorytm | edytuj kod

Algorytm szybkiego potęgowania jest konsekwencją obserwacji, że aby obliczyć wartość a b {\displaystyle a^{b}} wystarczy znać a b / 2 {\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ć 5 175 {\displaystyle 5^{175}} wystarczy znać wartość x = 5 87 , {\displaystyle x=5^{87},} a następnie policzyć y = x 2 = 5 174 {\displaystyle y=x^{2}=5^{174}} i wynik wynosi y 5. {\displaystyle y\cdot 5.} W ten sposób, aby wykonać jeden krok algorytmu, czyli przejść od 5 87 {\displaystyle 5^{87}} do 5 175 , {\displaystyle 5^{175},} wystarczy wykonać 2 mnożenia zamiast 88, jak wynikałoby to z przytoczonej wyżej definicji.

Pseudokod | edytuj kod

Z powyższych obserwacji można uzyskać rekurencyjną funkcję szybkiego obliczania wartości x n {\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 w {\displaystyle w} jest pamiętana n {\displaystyle n} -ta potęga liczby x {\displaystyle x} .

Na podstawie artykułu: "Algorytm szybkiego potęgowania" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy