lut 27 2017 27 lutego 2017 26 lutego 2017 przez Michał Franczak

Algorytm szybkiego potęgowania

Napisano w

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)} \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.

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.

Algorytm szybkiego potęgowania jest konsekwencją obserwacji, że aby obliczyć wartość a b {\displaystyle a^{b}} 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.

 

Tagi: