Potęgowanie iteracyjne

Potęgowanie iteracyjne polega na obliczeniu potęgi przez wielokrotne mnożenie tej samej liczby w pętli. Jest to prosty algorytm, często spotykany w zadaniach z analizy kodu.

Idea działania

Aby obliczyć a^b, należy pomnożyć liczbę a przez siebie b razy.

Przykład:

4^3 = 4 * 4 * 4 = 64

W programie można to zapisać za pomocą zmiennej pomocniczej, np. wynik, której początkowa wartość wynosi 1.

Przykład w C++

long int fun1(int a, int b)
{
    long int wynik = 1;
    for (int i = 0; i < b; i++)
        wynik *= a;
    return wynik;
}

Dla a = 4 i b = 3 działanie wygląda tak:

start: wynik = 1
1. obieg: wynik = 1 * 4 = 4
2. obieg: wynik = 4 * 4 = 16
3. obieg: wynik = 16 * 4 = 64

Funkcja zwraca więc 64.

Ważne szczegóły

• Zmienna wynik startuje od 1, ponieważ jest to element neutralny mnożenia.
• Liczba obiegów pętli zależy od wartości wykładnika b.
• Dla b = 0 wynik powinien pozostać równy 1, ponieważ każda liczba różna od zera podniesiona do potęgi zerowej daje 1.

Ten algorytm jest prosty, ale dla bardzo dużych wykładników istnieją szybsze metody, np. potęgowanie szybkie.