Szybkie potęgowanie

Zwane też "binarnym algorytmem potęgowania od prawej do lewej"

Algorytm ten powstał w celu nie innym, niż zmniejszenie złożoności w stosunku do potęgowania tradycyjnego. Ilość mnożeń potrzebna do obliczeń metody binarnej wynosi O(log_n), przy czym n oznacza wykładnik szukanej potęgi. Jest ona bardzo atrakcyjna w stosunku do innych metod. Niektóre z nic mogą mieć nawet złożoność wykładniczą !!!

Najlepiej zrozumieć istotę tego algorytmu poprzez analizę prostego kodu w C++.

//^^ Implementacja C++ by slic3 ^^
 
#include <iostream>
using namespace std;
 
int main()
{
cout<<"Podaj dowolna liczbe naturalna, ktora chcesz spotegowac: ";
 int x; cin>>x;
 
cout<<"Podaj wykladnik potegi: ";
 int p; cin>>p;
 
int y=1;  //zmienna, która stanowić będzie wynik potęgowania
 
   while(p!=0)
    {
    if(p%2==1) y=y*x; //operacja modulo dwa zapewne kojarzy się z zadaniem A (o rym wyszedł :D),
    p=p/2;                 //tutaj zawarta jest odpowiedź, dlaczego jest to potęgowanie binarne
    x=x*x;
    }
 
cout<<"Wynik: ";
cout<<y;
 
cout<<endl;
//system("PAUSE"); //odpalić w wypadku kompilacji nie na Puttym :) (dzięki temu program się nie zamyka)
}

Życzę powodzenia w zgłębianiu algorytmiki !!!
pozdrawiam,
slic3