Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VI edycja konkursu programistycznego

FRAKTAL

19-20 listopad 2016

czytaj więcej

Potęgowanie szybkie

powrót

Standardowe potęgowanie dla wyrażenia {tex}a^n{/tex} potrzebuje aż {tex}n-1{/tex} mnożeń, natomiast algorytm potęgowania szybkiego pozwala na wykonanie tego zadania wykonując maksymalnie {tex}2 \cdot log_2n{/tex} mnożeń - czyli bardzo szybko.

Dla przykładu popatrzmy na takie wyrażenie:

{tex}2^{10} = 2\cdot 2\cdot ... \cdot 2 = 1024{/tex}

Potęgę {tex}2^{10}{/tex} można rozpisać w inny sposób:

{tex}2^{10} = ( 2^5 )^2= ( 2 \cdot 2^4 )^2 =( 2 \cdot( 2^2 )^2 )^2 =( 2\cdot( 2\cdot 2 )^2 )^2{/tex}

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.

Więc gdzie jest ten złoty środek? Tak naprawdę wystarczy lepiej przyjrzeć się wykładnikowi i jego postaci binarnej, w tym przykładzie {tex}10 = (1010)_2{/tex}. Zasada jest następująca:

Ustawmy wynik = 1:

  • jeśli kolejny bit jest równy {tex}0{/tex} (licząc od prawej), podstawę nadpisujemy jej kwadratem
  • jeśli kolejny bit jest równy {tex}1{/tex}, wynik przemnażamy przez aktualną wartość podstawy, a podstawę nadpisujemy jej kwadratem.

 Czynności powtarzamy do wyczerpania bitów w liczbie.

Rozwiązanie iteracyjne:

#include<iostream>
using namespace std;
 
long long pot_szybkie(long long a, unsigned int n)
{
  long long w = 1;
 
  while(n>0)
  {
    if (n%2 == 1) //jesli bit jest = 1
      w *= a;
 
    a*= a;
    n/=2; //skrócenie o jeden bit
  }
  return w;
}
 
int main()
{
  unsigned int n;
  long long a;
 
  cout<<"Podaj podstawę: ";
  cin>>a;
  cout<<"Podaj wykładnik: ";
  cin>>n;
 
  cout<<a<<" do potęgi "<<n<<" wynosi "<<pot_szybkie(a, n);
 
  cin.get(); //czekamy na wcisnięcie klawisza
  return 0;
}
 

 

Rozwiązanie rekurencyjne:

#include<iostream>
 
using namespace std;
 
long long pot_szybkie(long long a, unsigned int n)
{
  if(n==0)
    return 1;
 
  if(n%2 == 1) //gdy n jest nieparzyste
    return a * pot_szybkie(a, n - 1);
 
  //żeby dwa razy nie wchodzić w tą samą rekurencję
  long long w = pot_szybkie(a, n/2); 
  return w * w;
}
 
int main()
{
  unsigned int n;
  long long a;
 
  cout<<"Podaj podstawę: ";
  cin>>a;
  cout<<"Podaj wykładnik: ";
  cin>>n;
 
  cout<<a<<" do potęgi "<<n<<" wynosi "<<pot_szybkie(a, n);
 
  cin.get(); //czekamy na wcisnięcie klawisza
  return 0;
}