====== Algorytm power ====== 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 =. ===== Nagłówek ===== Algorytm jest zdefiniowany w pliku nagłówkowym numeric lub też, niestandardowym, wstecznie kompatybilnym, algo.h. #include ===== Deklaracja (prototyp) power ===== Power jest przeładowaną nazwą. Istnieją dwie wersje algorytmu [[power]] template inline T power(T x, Integer n); template T power(T x, Integer n, MonoidOperation op); ===== Parametry ===== * //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); ===== Wartość zwracana ===== 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()). Druga wersja (power(T x, Integer n, MonoidOperation op) )jest podobna do pierwszej. Różnica polega na tym iż zamiast operacji * ( multiplies ) 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) ===== Działanie ===== 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. ===== Ostrzeżenie ===== 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ść. ===== Przykład użycia ===== ===Na obiektach klas wbudowanych:=== int main() { cout << "2 ** 30 = " << power(2, 30) << endl; } ===Na obiektach klasy zdefiniowanej przez użytkownika:=== 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 < ===Szablon klasy macierz:=== //definicja szablonu klasy macierzy kwadratowej ktora za parametr przyjmuje rozmiar tablicy template 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(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 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 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 struct mnozenie //: public binary_function, macierz, macierz> { macierz operator()(const macierz& x, const macierz& 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 macierz identity_element(mnozenie) { return macierz(1); };