Potęgowanie liczb według definicji

Załóżmy, że chcemy podnieść liczbę a do potęgi n. Aby wykonać to działanie, należy obliczyć iloczyn n czynników o wartości podstawy, czyli a.

an=aaan

Na przykład:

24=2222.

Iloczyn tych liczb można obliczyć za pomocą algorytmu iteracyjnegoiteracjaiteracyjnego oraz rekurencyjnegorekurencjarekurencyjnego.

Specyfikacja problemu:

Dane:

  • n – liczba naturalna; wykładnik potęgi

  • a – liczba całkowita różna od zera;  podstawa potęgi

Wynik:

Algorytm wypisuje wynik potęgowania .

Na początek przeanalizujmy schemat blokowy algorytmu w wersji iteracyjnej.

RuprVjxZ7tgsM1
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY 3.0.

Wykonanych zostanie n iteracji pętli, w których będą przeprowadzane operacje mnożenia aktualnej potęgi przez podstawę a. Zatem złożoność czasowa algorytmu potęgowania liczb według definicji wyrażona jako liczba wykonanych mnożeń wynosi .

Algorytm ten możemy przedstawić także za pomocą pseudokodu. W tym celu wykorzystamy instrukcję iteracyjną dla  wykonuj. Wewnątrz pętli umieścimy operację mnożenia aktualnej potęgi przez wartość podstawy potęgi.

Linia 1. potęga ← 1. Linia 2. dla i znak równości n przecinek n minus 1 przecinek kropka kropka kropka 1 wykonuj. Linia 3. potęga ← potęga asterysk a. Linia 4. wypisz potęga.

Szybkie potęgowanie liczb

Istnieje szybszy sposób potęgowania liczb od potęgowania według definicji.

Wersja iteracyjna szybkiego potęgowaniaszybkie potęgowanieszybkiego potęgowania oparta jest na dwójkowej reprezentacji wykładnika. Weźmy działanie . Liczba systemie dwójkowymsystem dwójkowy (system binarny)systemie dwójkowym to:

.

Możemy zapisać wartość tego wykładnika, korzystając ze schematu Hornera:

.

Metoda polega na pobieraniu kolejnych cyfr wykładnika zapisanego w systemie dwójkowym, zaczynając od lewej strony. Jeżeli ta cyfra ma wartość:

  • 0 – to aktualny wynik podnoszony jest do potęgi drugiej,

  • 1 – to aktualny wynik podnoszony jest do potęgi drugiej, a następnie mnożony jest przez podstawę.

Specyfikacja problemu:

Dane:

  • n – liczba naturalna w postaci binarnej ; wykładnik potęgi

  • x – liczba naturalna; liczba bitów w reprezentacji binarnej liczby n

  • a – liczba całkowita; podstawa potęgi

Wynik:

Algorytm zwraca wynik potęgowania .

Linia 1. potęga ← 1. Linia 2. dla i znak równości x przecinek x minus 1 przecinek kropka kropka kropka przecinek 1 wykonuj. Linia 3. bit ← cyfra liczby n na pozycji i. Linia 4. jeżeli bit znak równości 0. Linia 5. potęga ← potęga asterysk potęga. Linia 6. w przeciwnym razie. Linia 7. potęga ← potęga asterysk potęga asterysk a. Linia 8. wypisz potęga.

Powyższa metoda oparta jest na dwójkowej reprezentacji wykładnika. Liczby w systemie dwójkowym tworzone są od strony prawej (od najmniej znaczącego bitu), zatem jeżeli chcemy dotrzeć do poszczególnych bitów wykładnika zaczynając od lewej strony, należy najpierw użyć algorytmu konwersji liczby z systemu dziesiętnego na system binarny.

Analizując powyższy pseudokod algorytmu szybkiego potęgowania od lewej do prawej, możemy zauważyć, że liczba mnożeń zależna jest od liczby bitów w binarnej reprezentacji wykładnika. Złożoność algorytmu wynosi .

Ważne!

Obie zaprezentowane metody mają swoje wersje rekurencyjne. Ich omówienie oraz porównanie z wersjami iteracyjnymi znajdziesz w e‑materiale Analiza podejścia rekurencyjnego i iteracyjnegoPNMlyY9MbAnaliza podejścia rekurencyjnego i iteracyjnego.

Praca domowa

Zapisz zaprezentowane w e‑materiale algorytmy, wykorzystując wybrany język programowania.

Słownik

rekurencja
rekurencja

technika programowania polegająca na odwoływaniu się procedur lub funkcji do samych siebie, aż do momentu spełnienia warunku podstawowego

iteracja
iteracja

technika programowania polegająca na powtarzaniu tych samych operacji w pętli określoną liczbę razy lub do momentu, aż zostanie spełniony zadany warunek

schemat Hornera
schemat Hornera

sposób obliczania wartości wielomianu dla danej wartości argumentu wykorzystujący minimalną liczbę mnożeń

system dwójkowy (system binarny)
system dwójkowy (system binarny)

pozycyjny system liczbowy; sposób zapisywania liczb, w którym potrzebne są tylko dwie cyfry: , a podstawą tego systemu jest liczba

szybkie potęgowanie
szybkie potęgowanie

algorytm pozwalający na szybkie obliczenie potęgi liczby; wykorzystuje wykładnik zapisany w systemie dwójkowym