Szybkie Potęgowanie

Potęgowanie

Z definicji potęgowanie wynika, że podnosząc liczbę a do potęgi naturalnej n to: . W przypadku, gdy n = 0 to a⁰ = 1.

Implementując algorytm zgodnie z definicją otrzymujemy funkcję o złożoności rzędu Θ(n). Wydajność algorytmu możemy poprawić wiedząc, że a^{m + n} = a^m + aⁿ oraz a^mn = a^m·n. Załóżmy, że podnosimy a do potęgi n = 4. Wtedy a⁴=(a²)² - oznacza to, że wynik możemy uzyskać wykonując nie 4 mnożenia, a zaledwie dwa: najpierw podnosimy a do potęgi drugiej i wynik mnożymy przez niego samego.

Algorytm szybkiego potęgowania wykorzystuje ten fakt. Pozwala to na obliczenia potęgi o złożoności czasowej Θ(log n). Jednak tego typu potęgowania posiada ograniczenia dotyczące wykładnika n. Mianowicie . Co oznacza, że algorytm nie podniesie do dowolnej liczby podstawy.

Implementacja

Rozwiązanie algorytmu bardzo wygodnie zapisać jako rekurencje. W funkcji potęgując wyszczególnimy trzy przypadki - kiedy podnosimy do potęgi 0, kiedy podnosimy liczbę o wykładniku nieparzystym oraz parzystym:

1. double potega(double x, int n){
2.   if (n == 0)
3.     return 1;
4.   if (n % 2 != 0) {
5.     return x * potega(x, n - 1);
6.   } else {
7.     return pow(potega(x, n/2), 2.0);
8.   }
9. }

(1.) Funkcja przyjmuje dwa argumenty: x - jest to podstawa, a n to wykładnik. Należy pamiętać, że n musi być liczbą naturalną. Jako wynik zwrócimy wartość rzeczywistą. (2.) Jeśli wykładnik n = 0 to (3.) zwracamy wartość 1. (4.) Następnie sprawdzamy czy liczba jest nieparzysta. Tutaj wykorzystujemy fakt, że a^k = a · a^{k - 1}. (5.) Jako wynik zwracamy podstawę x pomnożoną przez wynik podnoszenia x do potęgi n - 1. Takie rozwiązanie pozwala na skorzystanie z (a^k)² w wywołanej rekurencji. (7.) Jeśli jednak wykładnik jest parzysty to obliczamy i wynik podnosimy do kwadratu.

Testowanie funkcji

Funkcję można przetestować przy pomocy poniższej funkcji. Należy pamiętać, że program nie sprawdza poprawności wprowadzonych danych. Tutaj należałoby dodać warunek sprawdzający czy podany wykładnik jest liczbą naturalną tj. czy n ≥ 0.

1. int main () {
2.   double x; int n;
3.   cin >> x >> n;
4.   cout << potega(x, n) << endl;
5.   system("pause");
6.   return 0;
7. }

• Kod źródłowy Implementacja

Dowolny wykładnik

Załóżmy, że chcemy, aby nasz wykładnik był liczbą całkowitą . Jak wiadomo . Innymi słowy nasza funkcja powinna podnosić x do |n|, a następnie podnieść do potęgi -1. W celu skorzystania z funkcji abs trzeba dołączyć bibliotekę cmtah.

1. double potega(double x, double n){
2.   return pow(potega(x, abs((int) n)), ((n < 0) ? -1 : 1));
3. }

(1.) Przeciążamy funkcję potega(). Ta część zostanie wywołana jeśli oba argumenty będą rzeczywiste. (W przypadku podawania liczby całkowitej dalej możemy używać typu int, ale nie chcemy zmieniać oryginalnej funkcji.) (2.) Zgodnie z założeniami x podnosimy do |n|. Wynik działania funkcji podnosimy z kolei do -1 lub 1. Mamy gotową funkcję, która obliczy wartość dla dowolnej liczby całkowitej.

Jednak czy jest możliwe podnoszenie do wykładnika rzeczywistego? Jeszcze nie, ale możemy rozdzielić wykładnik n na k i l zakładając, że , a . W ten sposób możemy obliczyć a^k przy pomocy dotychczas napisanej funkcji, a a^l przy pomocy standardowej funkcji pow(). Mnożąc obydwa wyniki przez siebie uzyskamy a^k·a^l = aⁿ).

1. double potega(double x, double n){
2.   return pow(pow(x, n - (int) n) * potega(x, abs((int) n)), ((n < 0) ? -1 : 1));
3. }

(2.) Dotychczasowy wynik funkcji potega() mnożymy przez część dziesiętną liczby n. Reszta zgodnie z poprzednią wersją funkcji. W ten sposób uzyskujemy funkcję algorytmu szybkiego potęgowania, która pozwala przyjąć jako wykładnik dowolną liczbę rzeczywistą.

Testowanie funkcji

W funkcji main() należy zmienić typ zmiennej n na double. Reszta bez zmian.

1. int main () {
2.   double x, n;
3.   cin >> x >> n;
4.   cout << potega(x, n) << endl;
5.   system("pause");
6.   return 0;
7. }

• Kod źródłowy Dowolny wykładnik