aby obliczyć wystarczy znać wartość a następnie policzyć i wynik wynosi W ten sposób, aby wykonać jeden krok algorytmu, czyli przejść od do wystarczy wykonać 2 mnożenia zamiast 88, jak wynikałoby to z przytoczonej wyżej definicji.
Pseudokod Z powyższych obserwacji można uzyskać rekurencyjną funkcję szybkiego obliczania wartości funkcja potęga(x, n) jeżeli n = 0 zwróć 1 jeżeli n jest nieparzysta zwróć x · potęga(x, n - 1) w przeciwnym przypadku a = potęga(x, n/2) zwróć a2
Po optymalizacji można otrzymać następującą postać:
funkcja potęga(x, n) jeżeli n = 0 zwróć 1 jeżeli n jest nieparzysta zwróć x · (potęga(x, (n - 1)/2))2 zwróć (potęga(x, n/2))2
Ten sam algorytm w wersji iteracyjnej wygląda następująco:
w:= 1 dla a = m do 1 // m - ilość miejsc binarnych liczby n c = a-ta cyfra binarna liczby n jeżeli c = 0 w:= w · w jeżeli c = 1 w:= w · w · x
po zakończeniu powyższego algorytmu w zmiennej jest pamiętana -ta potęga liczby
Linki zewnętrzne Szybkie potęgowanie – wykład, kanał Olimpiady Informatycznej Juniorów (OIJ) na YouTube, 14 listopada 2014 [dostęp 2023-11-24].
Kategoria:Algorytmy Kategoria:Potęgowanie