Szybkie potęgowanie – jak myśleć o potędze sprytniej, a nie ciężej

1. Wstęp – co to znaczy „szybkie potęgowanie”?

Gdy słyszysz potęgowanie, pewnie myślisz o czymś w stylu:
„2⁸ to 2×2×2×2×2×2×2×2” – osiem mnożeń.

To działa, ale… co jeśli chcesz policzyć 2¹⁰⁰⁰?
To tysiąc mnożeń – komputer zrobi to, ale bardzo nieefektywnie.
Dlatego programiści nauczyli komputery liczyć potęgi sprytniej – przez dzielenie problemu na pół.

To właśnie szybkie potęgowanie (ang. fast exponentiation lub exponentiation by squaring).

2. Prosty przykład z życia

Wyobraź sobie, że chcesz podwoić coś wiele razy – np. składany papier.
Zamiast za każdym razem liczyć od początku:

1. Złóż raz → 2 warstwy
2. Złóż drugi raz → 4 warstwy
3. Złóż trzeci raz → 8 warstw

Zauważ, że nie liczysz wszystkiego od zera – korzystasz z poprzedniego wyniku i go podnosisz do kwadratu.

To dokładnie idea szybkiego potęgowania:

zamiast mnożyć wielokrotnie, podnoś do kwadratu i łącz wyniki.

3. Jak działa potęgowanie „na piechotę”

Dla przypomnienia:

def potega_podstawowa(a, n):
    wynik = 1
    for i in range(n):
        wynik *= a
    return wynik

print(potega_podstawowa(2, 8))

def potega_podstawowa(a, n):
    wynik = 1
    for i in range(n):
        wynik *= a
    return wynik

print(potega_podstawowa(2, 8))

Wynik:

256

256

Ale komputer musiał wykonać 8 mnożeń.
Dla 2^1000 – aż 1000!
Można to zrobić w logarytmicznej liczbie kroków, czyli ok. 10 razy, nie 1000.

4. Pomysł: dziel przez dwa

Zauważmy, że:

• 2⁸ = (2⁴)²
• 2⁷ = (2³)² × 2

Czyli:

• gdy wykładnik jest parzysty, możemy go „połowić”:
  aⁿ = (a^(n/2))²
• gdy wykładnik jest nieparzysty, odejmujemy 1 i potem połówkujemy:
  aⁿ = a × (a^((n-1)/2))²

W ten sposób zamiast mnożyć n razy, dzielimy wykładnik na pół w każdej iteracji – jak w metodzie bisekcji!

5. Rekurencyjna wersja szybkiego potęgowania

def szybkie_potegowanie(a, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        polowa = szybkie_potegowanie(a, n // 2)
        return polowa * polowa
    else:
        polowa = szybkie_potegowanie(a, (n - 1) // 2)
        return a * polowa * polowa

print(szybkie_potegowanie(2, 8))
print(szybkie_potegowanie(3, 11))

def szybkie_potegowanie(a, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        polowa = szybkie_potegowanie(a, n // 2)
        return polowa * polowa
    else:
        polowa = szybkie_potegowanie(a, (n - 1) // 2)
        return a * polowa * polowa

print(szybkie_potegowanie(2, 8))
print(szybkie_potegowanie(3, 11))

Wynik:

256
177147

256
177147

Każde wywołanie dzieli wykładnik przez dwa, aż dojdzie do 1.
Wykonuje więc zaledwie log₂(n) kroków, czyli:

• dla 8 → 3 kroki
• dla 1000 → około 10 kroków!

6. Wersja iteracyjna (bez rekurencji)

Rekurencję można zastąpić pętlą — wtedy program działa szybciej i nie zużywa stosu.

def szybkie_potegowanie_iter(a, n):
    wynik = 1
    while n > 0:
        if n % 2 == 1:
            wynik *= a
        a *= a
        n //= 2
    return wynik

print(szybkie_potegowanie_iter(2, 10))

def szybkie_potegowanie_iter(a, n):
    wynik = 1
    while n > 0:
        if n % 2 == 1:
            wynik *= a
        a *= a
        n //= 2
    return wynik

print(szybkie_potegowanie_iter(2, 10))

Wynik:

1024

1024

Zasada ta sama:

• jeśli wykładnik nieparzysty → pomnóż wynik przez a,
• zawsze podnieś a do kwadratu,
• wykładnik podziel przez 2.

7. Porównanie – zwykłe vs szybkie

To ogromna różnica, szczególnie gdy komputer musi liczyć np. a^1000000.

8. Dlaczego to działa tak dobrze

Szybkie potęgowanie łączy w sobie:

• myślenie rekurencyjne – rozbijanie problemu na mniejsze części,
• metodę połowienia – dzielenie wykładnika przez 2,
• efektywność zachłanną – robisz tylko to, co konieczne w danym momencie.

To przykład algorytmu, który pokazuje, jak sprytny pomysł potrafi skrócić obliczenia z minut do sekund.

9. Zastosowania szybkiego potęgowania

• kryptografia – szyfrowanie danych w RSA i innych systemach,
• obliczenia naukowe – potęgowanie dużych macierzy,
• grafika komputerowa – szybkie transformacje i cieniowanie,
• symulacje fizyczne i gier – liczenie dużych potęg w czasie rzeczywistym.

10. Zadania dla ucznia

Zadanie 1 – Porównanie metod
Zaimplementuj dwie funkcje: zwykłe potęgowanie i szybkie potęgowanie.
Zlicz, ile razy każda z nich wykona mnożenie (np. przez zmienną licznik).
Porównaj wyniki dla 2⁸, 2¹⁶, 2³² i 2⁶⁴.

Zadanie 2 – Rekurencyjna wizualizacja
Dodaj do wersji rekurencyjnej print(n) w każdym kroku, żeby zobaczyć, jak wykładnik się zmniejsza.
Zauważ, że spada bardzo szybko.

Zadanie 3 – Duże liczby
Użyj funkcji szybkie_potegowanie_iter(2, 1000) i zobacz, jak szybko daje wynik.
Spróbuj potem dla 2**1000 i porównaj czas (np. z time.time()).

Zadanie 4 – Ujemny wykładnik
Rozszerz funkcję tak, by działała również dla n < 0, np. a^-3 = 1/(a^3).

11. Podsumowanie

12. Do zapamiętania

Szybkie potęgowanie to jak wspinaczka po schodach po dwa naraz – szybciej dojdziesz na szczyt, robiąc mniej kroków.

13. Dla wzrokowców

a^8
↓
(a^4)^2
↓
((a^2)^2)^2
↓
każdy krok dzieli wykładnik przez 2
↓
zamiast 8 mnożeń – tylko 3!