Potęgowanie szybkie

powrót

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

Dla przykładu popatrzmy na takie wyrażenie:

$$2^{10} = 2\cdot 2\cdot ... \cdot 2 = 1024$$

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

$$2^{10} = ( 2^5 )^2= ( 2 \cdot 2^4 )^2 =( 2 \cdot( 2^2 )^2 )^2 =( 2\cdot( 2\cdot 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.

Więc gdzie jest ten złoty środek? Tak naprawdę 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śli 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.

Rozwiązanie iteracyjne:

//algorytm.edu.pl
#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);

	return 0;
}

Rozwiązanie rekurencyjne:

//algorytm.edu.pl
#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);
	
	return 0;
}