Trzy podejścia do potęgowania
Programowanie...liczby naturalnej. Wikipedia stwierdza, że potęgowanie to działanie dwuargumentowe będące uogólnieniem wielokrotnego mnożenia elementu przez siebie. 2 do potęgi 3 to 2*2*2 = 8. Na podstawie tego przykładu można sądzić, że podniesienie liczby a do potęgi b wymaga b - 1 mnożeń. Otóż w trakcie lektury tego artykułu okaże się, że nie jest to prawdą. Zaprezentuję tu szybszy i bardziej efektywny algorytm. Zapraszam.
Klasyczne podejście
Iteracyjne potęgowanie jest w stanie napisać praktycznie każdy kto z programowaniem ma styczność, przychodzi to łatwo.
int potega(int podstawa, unsigned int wykladnik) {
int wynik = 1;
for(int i = 0; i < wykladnik; i++) {
wynik = wynik * podstawa;
}
return wynik;
}Funkcja działa dla całkowitej, niezerowej podstawy i naturalnego wykładnika. Przydałoby się dodać warunek, że 0 do potęgi 0 nie istnieje, lecz zaciemniłoby to przykład. Ogólna zasada działania opiera się na iteracyjnym przemnożeniu kolejno podstawy przez siebie tyle razy, ile wynosi wartość wykładnika. Gdy ten drugi jest równy 0, zwracana jest wartość 1 zgodnie z własnościami potęg. Funkcję można trochę usprawnić, pozbywając się zmiennej i:
int potega(int podstawa, unsigned int wykladnik) {
int wynik = 1;
for( ; wykladnik > 0 ; wykladnik--) {
wynik = wynik * podstawa;
}
return wynik;
}Pozbyliśmy się jednej zmiennej, nasza funkcja potrzebuje mniej pamięci. Wciąż jednak nie ma powodów do zadowolenia.
Podejście rekurencyjne
Dosyć łatwe do napisania, intuicyjnie zrozumiała zasada działania (jeśli tylko jesteśmy za pan brat z rekurencją)
int potega(int podstawa, unsigned int wykladnik) {
if(wykladnik == 0)
return 1;
return potega(podstawa, wykladnik-1)*podstawa;
}Zapis funkcji został znacznie skrócony, ale jest cena za prostotę. Narzut pamięci, wszystkie wywołania rekurencyjne będą znajdować się jednocześnie w pamięci aż do osiągnięcia najniższego jej stopnia.
Szybkie potęgowanie
Prezentowana poniżej funkcja działa szybciej niż prezentowane wyżej. Korzysta z następującej własności potęg, że liczba a do potęgi b*c, równa się liczbie a do potęgi i całości podniesionej do potęgi c. Przykład? 2 do potęgi 4 równie dobrze można przedstawić jako 2 do potęgi 2 i całość jeszcze raz do potęgi 2. Koniec końców wynik jest ten sam.
int potega(int podstawa, unsigned int wykladnik) {
int wynik = 1;
while(wykladnik > 0) {
if(wykladnik % 2 == 1) {
wynik = wynik * podstawa;
wykladnik--;
}
else {
podstawa = podstawa*podstawa;
wykladnik = wykladnik/2;
}
}
return wynik;
}