Lekcja 5. Szybkie potęgowanie — jak myśleć o potędze sprytniej, a nie ciężej
ŚredniPo co się tego uczymy?
Obliczenie 2¹⁰⁰⁰ "na piechotę" to tysiąc mnożeń — szybkie potęgowanie robi to samo w zaledwie 10 krokach. To trzeci, po wyszukiwaniu binarnym i bisekcji, przykład tej samej potężnej idei: dzielenia problemu na pół, tym razem zastosowanej do przyspieszania obliczeń wykorzystywanych m.in. w kryptografii RSA.
Teoria
Potęgowanie "na piechotę" — 2⁸ = 2×2×2×2×2×2×2×2, czyli 8 mnożeń. Dla 2^1000 to już 1000 mnożeń — działa, ale bardzo nieefektywnie.
Kluczowa obserwacja — zauważmy, że 2⁸ = (2⁴)² oraz 2⁷ = (2³)² × 2. Stąd wzór:
- gdy wykładnik jest PARZYSTY:
aⁿ = (a^(n/2))²— możemy go "połowić"; - gdy wykładnik jest NIEPARZYSTY:
aⁿ = a × (a^((n-1)/2))²— odejmujemy 1 i połówkujemy.
Zamiast mnożyć n razy, DZIELIMY WYKŁADNIK na pół w każdej iteracji — dokładnie jak w metodzie bisekcji (poprzednia lekcja), tylko zastosowanej do zupełnie innego problemu.
Złożoność: zamiast O(n) mnożeń, szybkie potęgowanie wykonuje zaledwie O(log₂ n) kroków — dla 8 to 3 kroki, dla 1000 to około 10 kroków!
| Potęga n | Zwykła metoda (liczba mnożeń) | Szybkie potęgowanie |
|---|---|---|
| 4 | 4 | 2 |
| 8 | 8 | 3 |
| 16 | 16 | 4 |
| 1000 | 1000 | 10 |
Wersja iteracyjna (bez rekurencji) działa szybciej i nie zużywa pamięci stosu — zasada: jeśli wykładnik NIEPARZYSTY, pomnóż wynik przez a; ZAWSZE podnieś a do kwadratu; wykładnik podziel przez 2 (całkowicie).
Dlaczego to działa tak dobrze — szybkie potęgowanie łączy myślenie rekurencyjne (rozbijanie problemu na mniejsze części), metodę połowienia (dzielenie wykładnika przez 2) i "zachłanną" efektywność (robisz tylko to, co konieczne w danym momencie).
Zastosowania: kryptografia (szyfrowanie RSA i inne systemy wymagają potęgowania OGROMNYCH liczb — bez szybkiego potęgowania byłoby to praktycznie niewykonalne), obliczenia naukowe, grafika komputerowa (transformacje, cieniowanie), symulacje fizyczne i gier.
Schemat
a^8 ↓ (a^4)^2 ↓ ((a^2)^2)^2 ↓ każdy krok DZIELI wykładnik przez 2 ↓ zamiast 8 mnożeń – tylko 3! Wykładnik nieparzysty (np. n=11): a^11 = a × (a^5)^2 = a × ((a × (a^2)^2))^2 ... (odejmij 1, podziel przez 2, pamiętaj o dodatkowym "razy a")
Przykład z życia
Składanie kartki papieru wielokrotnie na pół (za każdym razem grubość się PODWAJA) to codzienna intuicja stojąca za szybkim potęgowaniem — zamiast liczyć grubość od zera przy każdym złożeniu, korzystasz z POPRZEDNIEGO wyniku i podnosisz go do kwadratu. Dokładnie tak działa RSA — jeden z najpopularniejszych systemów szyfrowania w internecie, który wymaga potęgowania liczb o SETKACH cyfr; bez szybkiego potęgowania każde logowanie do banku trwałoby wieki.
szybkie_potegowanie.py
# Potęgowanie "na piechotę" - dla porównania
def potega_podstawowa(a, n):
wynik = 1
for i in range(n):
wynik *= a
return wynik
print(potega_podstawowa(2, 8))
# Wynik: 256 (ale 8 mnożeń)
# Szybkie potęgowanie - wersja rekurencyjna
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)) # 256, tylko 3 mnożenia
print(szybkie_potegowanie(3, 11)) # 177147szybkie_potegowanie_iteracyjne.py
# Szybkie potęgowanie - wersja iteracyjna (bez rekurencji, szybsza)
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: 1024Komentarz i wyjaśnienie kodu
W wersji rekurencyjnej zauważ RÓŻNICĘ między przypadkiem parzystym i nieparzystym: dla parzystego wykładnika wystarczy policzyć a^(n/2) RAZ i podnieść do kwadratu (polowa * polowa), a dla nieparzystego trzeba DODATKOWO domnożyć przez a (bo dzielenie całkowite (n-1)//2 "gubi" jedną jednostkę wykładnika).
Wersja iteracyjna robi coś subtelnego: w KAŻDEJ iteracji a jest podnoszone do kwadratu (a *= a), niezależnie od tego, czy aktualny bit wykładnika jest ustawiony — ale wynik MNOŻYMY przez a TYLKO wtedy, gdy n jest w danym momencie nieparzyste (n % 2 == 1). To odzwierciedla binarny (dwójkowy) zapis wykładnika — każdy bit "decyduje", czy dana potęga a wchodzi do wyniku.
Ćwiczenie samodzielne
Uruchom obie wersje (rekurencyjną i iteracyjną) dla kilku różnych par (a, n) i sprawdź, że dają identyczne wyniki. Dodaj do wersji rekurencyjnej print(n) na początku funkcji, żeby zobaczyć, jak szybko wykładnik maleje.
Zadania do pracy własnej
Zaimplementuj obie funkcje (zwykłe i szybkie potęgowanie) z licznikiem mnożeń (zmienna globalna lub dodatkowy parametr) i porównaj liczbę wykonanych mnożeń dla 2⁸, 2¹⁶, 2³² i 2⁶⁴.
Użyj funkcji
szybkie_potegowanie_iter(2, 1000)i zmierz czas jej wykonania (modułtime), a następnie porównaj z czasem zwykłego2**1000wbudowanego w Pythona — dlaczego wynik może Cię zaskoczyć (wskazówka: Python sam wewnętrznie optymalizuje operator**)?Rozszerz funkcję szybkiego potęgowania tak, żeby działała również dla WYKŁADNIKA UJEMNEGO, wykorzystując wzór
a^(-n) = 1 / (a^n). Przetestuj dla kilku wartości i porównaj z wynikiem operatora**w Pythonie.
Typowe błędy
Zapominanie o dodatkowym mnożeniu przez a dla NIEPARZYSTEGO wykładnika — bez tego kroku wynik będzie systematycznie zaniżony (bo (n-1)//2 "traci" połowę jedynki wykładnika).
Nieskończona rekurencja przy braku warunku stopu (if n == 0: return 1) — bez tego warunku funkcja rekurencyjna nigdy się nie zatrzyma.
Przekonanie, że szybkie potęgowanie ZAWSZE trzeba pisać samodzielnie — w praktyce Python (i większość języków) wewnętrznie optymalizuje operator potęgowania (**) podobną techniką, ale rozumienie MECHANIZMU jest kluczowe dla egzaminu i dla sytuacji, gdy potrzebujesz np. potęgowania modulo (częste w kryptografii).
Nawiązanie do egzaminu zawodowego
Szybkie potęgowanie to trzeci przykład strategii "dziel na pół" w tym dziale (po wyszukiwaniu binarnym i metodzie bisekcji) — pokazuje, że TA SAMA idea algorytmiczna sprawdza się w bardzo różnych kontekstach. W kolejnej lekcji zobaczysz rekurencję w jeszcze innych zastosowaniach — ciąg Fibonacciego i fraktale.