Jakub Piskorowski on 30/08/2023 wersja: 1.0
Przedstawienie działania algorytmu szybkiego potęgowania.
Kod źródłowy: iteracyjnie-szybkie-potegowanie.cpp
📒 Poziom 2
Powrót do Algorytmika
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), gdzie n oznacza wykładnik obliczanej potęgi.
Standardowe potęgowanie dla wyrażenia an potrzebuje aż n-1 mnożeń, natomiast algorytm potęgowania szybkiego pozwala na wykonanie tego zadania wykonując maksymalnie 2*log2n mnożeń, czyli bardzo szybko.
Dla przykładu popatrzmy na takie wyrażenie:
210 = 2* 2*...*2 = 1024
Potęgę
210
można rozpisać w inny sposób:
210=(25)2= (2 * 24)2=(2 * (22)2)2 = (2 * (2 * 2)2)2
Licząc ilość mnożeń otrzymujemy w tym przypadku tylko cztery. Dla dużych wykładników oszczędność jest ogromna. Gdybyśmy chcieli podnieść do potęgi miliard, wykonalibyśmy nie więcej niż 100 mnożeń a więc się opłaca.
Tak na prawdę wystarczy lepiej przyjrzeć się wykładnikowi i jego postaci binarnej, w tym przykładzie.
10 = ( 1010 )2
Zasada jest następująca:
Ustawmy wynik = 1:
jeżeli kolejny bit jest równy 0 (licząc od prawej), podstawę nadpisujemy jej kwadratem.
jeśli kolejny bit jest równy 1, wynik przemnażamy przez aktualną wartość podstawy, a podstawę nadpisujemy jej kwadratem.
Czynności powtarzamy do wyczerpania bitów w liczbie.
Wejście:
a – podstawa
n - wykładnik
Wyjście:
w - wynik potęgowania szybkiego
Lista kroków:
K1: w ← 1 początkowa wartość zmiennej przechowującej wynik
K2: dopóki n > 0
wykonuj kroki K3...K5
K3: jeżeli n modulo 2 = 1 jeżeli bit jest równy 1
to w ← w * a
K4: a ← a * a
K5: n ← n \ 2
K6: zwróć w
Wynik działania programu:
Podaj podstawe: 2
Podaj wykladnik: 6
2 do potegi 6 wynosi: 64
Kod źródłowy: iteracyjnie-szybkie-potegowanie.cpp