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$.

Na przykład:

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 $a^n$.

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

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 $O\left( n\right)$.

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

potęga ← 1
dla i = n, n - 1, ... 1 wykonuj
	potęga ← potęga * a
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 $3^{14}$. Liczba $14$ w 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 $n_x\ n_{x-1}\ n_{x-2}\dots n_1$; 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 $a^n$.

potęga ← 1
dla i = x, x - 1, ..., 1 wykonuj
	bit ← cyfra liczby n na pozycji i
	jeżeli bit = 0
		potęga ← potęga * potęga
	w przeciwnym razie
		potęga ← potęga * potęga * a
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 $O\left(\log_2n\right)$.

Słownik