Algorytm power podnosi obiekt dowolnej klasy (o ile spełnia pewne wymagania) do zadanego wykładnika będącego nieujemną liczbą całkowitą. Algorytm korzysta z operatora *, dlatego też, aby używać funkcji szablonowej power na własnych klasach należy przeładować operatory * oraz =.

Algorytm jest zdefiniowany w pliku nagłówkowym numeric lub też, niestandardowym, wstecznie kompatybilnym, algo.h.

 #include <numeric> 

Power jest przeładowaną nazwą. Istnieją dwie wersje algorytmu power

template <class T, class Integer>
inline T power(T x, Integer n);
 
template <class T, class Integer, class MonoidOperation>
T power(T x, Integer n, MonoidOperation op);

• x – obiekt klasy typu T tworzącej monoid (półgrupa z działaniem które ma element neutralny); x może być typu wbudowanego (int, float) jak również typu zdefiniowanego przez programistę; ważne jest aby na elementach tego typu była wykonywalna operacja mnożenia (niekoniecznie trywialna);
• n – nieujemna liczba całkowita; ważne by typ Integer był zgodny z typem wbudowanym int;

Oraz występujący w drugiej wersji power:

• op – obiekt klasy funkcyjnej (funktor), definiującej działanie, które ma wykonywać algorytm ( w szczególności może to być mnożenie elementów);

Obie wersje algorytmu zwracają obiekt takiego samego typu jak pierwszy argument funkcji.

power(T x, Integer n) zwraca wartość x * x …. * x, gdzie x jest powtórzone n razy. Kiedy n = 0, wartość zwracana wynosi identity_element(multiplies<T>()).

Druga wersja (power(T x, Integer n, MonoidOperation op) )jest podobna do pierwszej. Różnica polega na tym iż zamiast operacji * ( multiplies<T> ) wykonywana jest operacja op. Kiedy n = 0 funkcja zwraca identity_element(op). Obie funkcje należy zdefiniować, tworząc np. funktor oraz przeładowując identity_element(). (patrzy przykład poniżej)

Ponieważ kolejne mnożenie przez siebie kolejnych wartości (n-1 razy) byłoby nieefektywne, power implementuje „algorytm chłopów rosyjskich”. Jego złożoność obliczeniowa wynosi log2(n) + n1(n) gdzie log2 jest logarytmem o podstawie 2 z liczby n, a n1(n) jest liczbą jedynek w zapisie binarnym liczb n. Nie zawsze power wykonuje minimalną liczbę mnożeń; np. możliwe jest podniesienie wartości do potęgi piętnastej wykonując tylko pięć operacji mnożenia; power() wykonuje sześć. Dla prostych elementów nie powoduje to znaczącej różnicy, ale dla np. wielowymiarowych macierzy własna metoda podnoszenia do potęgi mogłaby być efektywniejsza czasowo.

Algorytm power nie wymaga aby operacja mnożenia na obiektach typu T była przemienna, natomiast krytyczne jest aby operacja ta była łączna. Jeśli operacja * lub op na obiektach klasy T nie jest łączna wtedy power zwróci złą wartość.

int main() {
  cout << "2 ** 30 = " << power(2, 30) << endl;
}

void main(void)
{
	//stworzenie macierzy o wymiarze 3x3 zawierajacej 2 na przekątnej
	macierz<3> pierwsza(2);
	//wstawienie 4 na miejscu (1,2) oraz (3,2) - pola są numerowane od 1 do wymiar
	pierwsza.wstaw(1,2,4);
	pierwsza.wstaw(3,2,4);
	//wyswietlenie przykladowo stworzonej macierzy
	cout << pierwsza << "\n";
 
	//stworzenie macierzy jednostkowej i jej wyswietlenie na ekranie
	macierz<3> druga(1);
	cout << druga << "\n";
 
	// stworzenie macierzy zerowej; dodanie pierwszej i drugiej oraz przypisanie sumy do trzeciej
	macierz<3> trzecia;
	trzecia = pierwsza + druga;
	cout << trzecia << "\n";
 
	//wyswietlenie wyniku dla operacji power(x,0) 
	//w przypadku macierzy wynikiem takiej operacji jest maciez jednostkowa
	//pierwszy rodzaj algorytmu power
	cout << power(trzecia,0) << "\n";
	//drugi rodzaj algorytmu power
	cout << power(trzecia,0,mnozenie<3>()) << "\n";
 
	//stworzenie macierzy zerowej i przypisanie do niej wyniku podnoszenia macierzy do potegi 3
	macierz<3> czwarta;
	czwarta = power(trzecia,3,mnozenie<3>());
	cout <<czwarta << "\n";
}

//definicja szablonu klasy macierzy kwadratowej ktora za parametr przyjmuje rozmiar tablicy 
template <int rozmiar>
class macierz
{
private:
	int rodzaj;	// 0 identycznosciowa dla operacji dodawania; 1 identycznosciowa dla operacji mnozenia
	float tablica[rozmiar][rozmiar];
 
public:
	//destruktor
	~macierz(void){};
	//konstruktor bezargumentowy inicjuje tablice zerami
	macierz(void)
	{
		for( int i = 0; i < rozmiar; i++)
		{
			for (int j = 0; j < rozmiar; j++)
			{
				tablica[i][j] = 0.0;
			}
		}
	};
	//konstruktor kopiujacy
	macierz(const macierz& M)
	{
		rodzaj = M.rodzaj;
		for( int i = 0; i < rozmiar; i++)
		{
			for (int j = 0; j < rozmiar; j++)
			{
				tablica[i][j] = M.tablica[i][j];
			}
		}
		//*this = M; 
	};
	//konstruktor przyjmujący argument klasy int pozwalający tworzyć macierz jednostkową: macierz<rozmiar>(1)
	//kontruktor ten tworzy macierz wypelniona zerami oprocz przekatnej gdzie znajduja sie jedynki
	//niezbedny dla wlasciwego dzialania operacji power ktora dla zerowego wykladnika zwraca wartosc __T(0) gdzie __T jest obiektem klasy dla ktorej wywolany zostal algorym power
	macierz(int x )
	{
		rodzaj = x;
		for( int i = 0; i < rozmiar; i++)
		{
			for (int j = 0; j < rozmiar; j++)
			{
				if( i == j) 
					tablica[i][j] = (float)rodzaj;
				else 
					tablica[i][j] = 0;
			}
		}
	};
	//przeladowany operator przypisania niezbedny dla poprawnego dzialania algoryty power, ktory wykorzystuje przypisanie wczasie wykonywania iloczynow czesciowych
	macierz& operator=( const macierz& M)
	{
		rodzaj = M.rodzaj;
		for( int i = 0; i < rozmiar; i++)
		{
			for (int j = 0; j < rozmiar; j++)
			{
				tablica[i][j] = M.tablica[i][j];
			}
		}
		return *this;
	};
	//przeladowany operator mnozenia niezbedny dla poprawnego dzialania algorytmu power(T x, Integer n)
	//w algorytmie (T x, Integer n, MonoidOperation op) sami mozemy zdefiniowac ktora operacja ma byc wykonywana na obiekcie x klasy T
	macierz operator*( const macierz& M) const
	{
		macierz<rozmiar> temp;
		for( int i = 0; i < rozmiar; i++)
		{
			for (int j = 0; j < rozmiar; j++)
			{
				for (int k = 0; k < rozmiar; k++)
					temp.tablica[i][j] += tablica[i][k] * M.tablica[k][j];
			}
		}
		return temp;
	};
	//przeladowany operator dodwania - przydatny przy testowaniu klasy 
	macierz operator+( const macierz& M) const
	{
		macierz<rozmiar> temp;
		for( int i = 0; i < rozmiar; i++)
		{
			for (int j = 0; j < rozmiar; j++)
			{
				temp.tablica[i][j] = tablica[i][j] + M.tablica[i][j];
			}
		}
		return temp;
	};
	//przeladowany operator na klasie ostream; sluzy do wypisania wyniku; przydatny przy testowaniu
	friend ostream& operator<<(ostream& wy, const macierz& M)
	{
		for( int i = 0; i < rozmiar; i++)
		{
			for (int j = 0; j < rozmiar; j++)
			{
				wy << M.tablica[i][j] << "\t"; 
			}
			wy << "\n";
		}
	return wy;
	};
	//metoda klasy sluzaca do ustawiania wartosci w tablicy
	//x oraz y sa z zakresu 1.. rozmiar - konwencja bardziej naturalna 
	void wstaw(int x, int y, float wartosc)
	{
		if ( ( x > 0 ) && ( x <= rozmiar ) && ( y > 0 ) && ( y <= rozmiar ) )
			tablica[x-1][y-1] = wartosc;
	};
	//macierz& operator+=( const macierz &);
	//macierz& operator*=( const macierz &);
};
 
//funktor - klasa definiujaca operator mnozenia dla klasy macierz. 
//wlasciwie jest tutaj wykorzystany operator * zdefiniowany wewnatrz klasy
//ale mozna utworzyc wlasna metode mnozenia, np bardziej efektywna gdybysmy uzywali specjalnego rodzaju klas ipt. i latwo podmieniać w wywolaniu algorytmu power
template <int rozmiar>
struct mnozenie //: public binary_function<macierz<rozmiar>, macierz<rozmiar>, macierz<rozmiar>> 
{
  macierz<rozmiar> operator()(const macierz<rozmiar>& x, const macierz<rozmiar>& y) const 
  { 
	  return x * y;
  }
};
 
//przeladowana funkcja zwracajaca element identycznosciowy dla mnozenia macierzy
//tak jak wyzej mozna przeladowac ja wiele razy w zaleznosci od operacji mnozenia
template <int rozmiar>
macierz<rozmiar>	identity_element(mnozenie<rozmiar>) {
	return macierz<rozmiar>(1);  
};