Wstęp – po co szybkie potęgowanie?

Zadanie: obliczyć $a^n$.

• Naiwnie (na podstawie definicji): mnożymy $a$ przez siebie n razy → O(n) operacji mnożenia.

• Lepiej: wykorzystać fakt, że:

  • $a^{2k}=(a^k{)}^2$

  • $a^{2k+1}=a\cdot (a^k{)}^2$

Dzięki temu zmniejszamy wykładnik o połowę w każdym kroku.
To podejście nazywa się szybkim potęgowaniem (ang. fast exponentiation) i działa w czasie O(log n).

Implementacja algorytmu szybkiego potęgowania (wersja rekurencyjna)

def szybkie_potegowanie(a, n):
    # przypadek podstawowy
    if n == 0:
        return 1

    # rekurencyjne obliczenie a^(n//2)
    polowa = szybkie_potegowanie(a, n // 2)

    # jeśli n jest parzyste
    if n % 2 == 0:
        return polowa * polowa
    else:
        return a * polowa * polowa

Jak działa algorytm?

Przykład: obliczmy $2^{13}$

1. $2^{13}=2\cdot (2^6{)}^2$

2. $2^6=(2^3{)}^2$

3. $2^3=2\cdot (2^1{)}^2$

4. $2^1=2\cdot (2^0{)}^2$

5. $2^0=1$

Algorytm:

• dzieli problem na mniejszy (rekurencja),

• zapamiętuje wynik połowy,

• składa wynik w drodze powrotnej.

Implementacja iteracyjna (dla porównania)

def szybkie_potegowanie_iter(a, n):
    wynik = 1

    while n > 0:
        if n % 2 == 1:
            wynik *= a
        a *= a
        n //= 2

    return wynik

Jak działa program?

• Gdy wykładnik jest nieparzysty → mnożymy dodatkowo przez a

• Podnosimy a do kwadratu

• Dzielimy wykładnik przez 2

• Powtarzamy, aż n == 0