Szybkie potęgowanie

Działanie algorytmu:

Szybkie potęgowanie ma na celu podniesienie liczby do danej potęgi wykonując jak najmniejszą liczbę mnożeń.

Chcąc podnieść liczbę 2 do potęgi 10 normalnie zrobilibyśmy to w ten sposób:

czyli wykonalibyśmy n-1, czyli 9 mnożeń.

Wykorzystując jednak algorytm szybkiego potęgowania wykonamy jednak tylko , czyli 4 mnożenia:

czyli wykonalibyśmy n-1, czyli 9 mnożeń.

Wykorzystując jednak algorytm szybkiego potęgowania wykonamy jednak tylko , czyli 4 mnożenia:

Złożoność naszego algorytmu wynosi więc O(log N).

Przeanalizujmy teraz sposób działania algorytmu:

Naszą liczbą, którą chcemy podnieść do potęgi będzie a (2).

Potęgą do jakiej chcemy podnieść a będzie n (10)

Zmienna wynik będzie przechowywać ostateczną wartość naszego potęgowania

Zoptymalizowany algorytm polega na zamianie potęgi (n) na system binarny, a następnie wykonaniu liczby mnożeń zależnej od występujących kolejno od tyłu bitów.

DLA 0:

, ponieważ oznacza to, że potęga jest parzysta

DLA 1:

, ponieważ oznacza to, że potęga jest nieparzysta

Przeanalizujmy działanie naszego algorytmu dla kolejnych danych:

Wynikiem naszego potęgowania jest zmienna wynik, czyli 1024

Przykładowa implementacja:

#include <iostream>
using namespace std;
int fast_exponentiation(int a, int n)
//tworzymy funkcję, która przyjmuje dwa argumenty, a - liczbę oraz n - potęgę
{
    int wynik=1; //tworzymy zmienną która będzie zawierała nasz wynik
    while(n>0) 
    //rozpoczynamy pętle, która będzie działała dopóki nasza potęga 
    //będzie większa od 0
    {
        if(n%2==1)	
        //sprawdzamy czy nasz bit (n%2) jest równy 1, jeśli tak to mnożymy wynik *a
            wynik*=a;
        a*=a; //w każdym przypadku mnożymy a przez samą siebie
        n/=2; //przechodzimy do kolejnego bitu
    }	
    return wynik; //zwracamy wynik naszej funkcji
}
int main()
{
    int a,n;
    cin>>a>>n; //tworzymy dwie zmienne i wczytujemy liczbę oraz potęgę od użytkownika
    cout<<fast_exponentiation(a,n);	//wywołujemy naszą funkcję dla podanych liczb
    return 0;
}