Szybkie potęgowanie

🎯 Po co Ci to?

Gdy logujesz się do banku, Twój telefon oblicza — w ułamku sekundy — potęgę o wykładniku mającym sześćset cyfr (zobaczysz to w 5.7). Licząc naiwnie, mnożenie po mnożeniu, potrzebowałby $10^{600}$ operacji: wszechświat zdąży ostygnąć. A jednak kłódka przy adresie zapala się natychmiast. Sztuczka, która to umożliwia, ma dwa składniki, które już znasz — podwajanie i zapis dwójkowy — i jest ostatnim „przyspieszaczem" tego działu. Po niej będziesz patrzeć na wykładniki jak na ciągi bitów.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

policzyć $a^n$ metodą podwajania w około $\log_2 n$ mnożeń — rekurencyjnie i iteracyjnie;
wyjaśnić związek wersji iteracyjnej z zapisem dwójkowym wykładnika;
uzasadnić liczbę mnożeń logarytmem (i sprawdzić ją na przykładach).

🔁 Przypomnij sobie

Z 1.4/2.7: połowienie i $\log_2$; z 2.1: zapis dwójkowy; z 4.3: rekurencja z przypadkiem bazowym.

📘 Wyjaśnienie

Obserwacja-fundament. Po co liczyć $a^{16}$ szesnastoma mnożeniami, skoro $a^{16} = (a^8)^2$? A $a^8 = (a^4)^2$, $a^4 = (a^2)^2$… Cztery podniesienia do kwadratu zamiast piętnastu mnożeń. Dla wykładników nieparzystych jeden ruch ratunkowy: $a^{13} = a \cdot a^{12}$. Razem daje to przepis rekurencyjny:

$$a^n = \begin{cases} 1 & \text{dla } n = 0 \ (a^{n/2})^2 & \text{dla } n \text{ parzystych} \ a \cdot a^{n-1} & \text{dla } n \text{ nieparzystych} \end{cases}$$

def potega(a, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        w = potega(a, n // 2)
        return w * w               # UWAGA: policz raz, pomnóż przez siebie!
    return a * potega(a, n - 1)

Wykładnik co najwyżej co drugi krok maleje o połowę — więc mnożeń jest około $2\log_2 n$: dla $n$ = miliard — sześćdziesiąt, nie miliard. Znów logarytm robi z niemożliwego rutynę.

⚠️ Uwaga, pułapka: linijka w = potega(...); return w * w to nie pedanteria. Gdyby napisać return potega(a, n//2) * potega(a, n//2), funkcja liczyłaby dwa razy to samo — i drzewo wywołań rozrosłoby się do pełnych $n$ mnożeń. Cały zysk algorytmu wyparowuje w jednej linijce. To ta sama choroba, co u naiwnego Fibonacciego (4.3): powtarzanie podproblemów. Morał na życie: zanim wywołasz coś dwa razy, zapytaj, czy nie znasz już wyniku.

Wersja iteracyjna: bity wykładnika. Rozpisz $a^{13}$ przez zapis dwójkowy wykładnika: $13 = 1101_2 = 8 + 4 + 1$, więc

$$a^{13} = a^8 \cdot a^4 \cdot a^1$$

Potęgi o wykładnikach 1, 2, 4, 8… buduje się kolejnymi kwadratami, a do wyniku bierze te, przy których bit wykładnika jest zapalony. Kod czyta bity od najmłodszego:

def potega_iter(a, n):
    wynik = 1
    skladnik = a                   # kolejno: a¹, a², a⁴, a⁸, ...
    while n > 0:
        if n % 2 == 1:             # najmłodszy bit zapalony?
            wynik = wynik * skladnik
        skladnik = skladnik * skladnik
        n = n // 2                 # zsuń bity o jeden w prawo
    return wynik

Para operacji n % 2 (odczytaj bit) i n //= 2 (przejdź do następnego) to dokładnie metoda zamiany na system dwójkowy z jednostki 2.1! Szybkie potęgowanie czyta wykładnik binarnie — Horner robił z konwersji obliczanie wielomianu, tu konwersja steruje mnożeniami. Dwa działy tej książki podają sobie ręce po raz drugi w ciągu dwóch jednostek.

🧮 Prześledź

Prześledź potega_iter(3, 13):

obrót	bit (`n % 2`)	`wynik` po	`skladnik` po	`n` po
start	—	1	3	13
1	?	?	?	?
2	?	?	?	?
3	?	?	?	?
4	?	?	?	?

Sprawdź odpowiedź

Obrót 1: bit 1 → wynik 3; składnik 9; $n=6$. Obrót 2: bit 0 → wynik 3; składnik 81; $n=3$. Obrót 3: bit 1 → wynik 243; składnik 6561; $n=1$. Obrót 4: bit 1 → wynik $243 \cdot 6561 = 1,594,323$; $n=0$. I rzeczywiście $3^{13} = 1,594,323$ ✓ — pięć mnożeń „składnikowych" plus trzy „wynikowe" zamiast dwunastu naiwnych. Bity 1101 czytane od prawej: 1, 0, 1, 1 — zgadza się z kolumną bitów.

🤯 Ciekawostka

Metodę podwajania wykładnika znali już staroindyjscy matematycy (traktat Pingali o rytmach poezji, ~200 p.n.e. — liczyli nią liczbę układów sylab!). W kryptografii używa się jej w wariancie „potęgowanie modulo": po każdym mnożeniu bierze się resztę z dzielenia przez ustaloną wielką liczbę, więc wyniki nigdy nie puchną, a 60 mnożeń liczb 600-cyfrowych to dla procesora spacerek. Bez tej sztuczki bezpieczny internet po prostu by nie istniał — za wolno by się łączył.

🛠️ Teraz Ty

Bez komputera: rozpisz $2^{21}$ metodą bitów ($21 = 10101_2$) — które potęgi wchodzą do iloczynu i ile mnożeń łącznie? Z komputerem: zaimplementuj obie wersje; dołóż licznik mnożeń i wypisz go dla $n$ = 15, 16, 1000, 10⁶. Porównaj z $\log_2 n$ — trzyma się?

📐 Definicje tej lekcji

Szybkie potęgowanie — $a^n$ w $O(\log n)$ mnożeń: rekurencyjnie przez $(a^{n/2})^2$, iteracyjnie przez kwadraty i bity wykładnika.

📌 Najważniejsze w pigułce

Kwadrat połówki zamiast mnożenia po mnożeniu: miliardowa potęga w ~60 krokach.
w = potega(n//2); w * w — policz raz; podwójne wywołanie zabija cały zysk.
Wersja iteracyjna czyta wykładnik jak liczbę dwójkową: bit zapalony = domnóż bieżący kwadrat.

🎒 Zadania

Ile mnożeń (dokładnie, licząc oba rodzaje) wykonuje potega_iter dla $n = 15$, a ile dla $n = 16$? Dlaczego „większy" wykładnik bywa tańszy?

Wskazówka i odpowiedź

$15 = 1111_2$: cztery obroty, cztery bity zapalone — 4 mnożenia wynikowe + 3 składnikowe (ostatnie podwojenie i tak się liczy… licząc dokładnie z kodu: 4 + 4 = 8, z czego jedno składnikowe nadmiarowe). $16 = 10000_2$: pięć obrotów, jeden bit — 1 + 4 = 5. Mniej jedynek w zapisie = mniej mnożeń wynikowych; koszt zależy nie tylko od wielkości $n$, ale i od jego budowy bitowej. Algorytmy widzą liczby inaczej niż oś liczbowa.

Napisz potega_mod(a, n, m) liczącą $a^n \bmod m$ (po każdym mnożeniu bierz % m). Policz $7^{128} \bmod 13$ i wyjaśnij, czemu wyniki pośrednie nigdy nie przekraczają $(m-1)^2$.

Wskazówka i odpowiedź

Wystarczy w obu miejscach mnożenia dopisać % m. $7^{128} \bmod 13$: kolejne kwadraty mod 13: $7 \to 10 \to 9 \to 3 \to 9 \to 3 \to 9 \to 3$; $128 = 10000000_2$ (jeden bit) → wynik to ósmy element: 3. Skoro każdy czynnik jest resztą ($< m$), iloczyn przed redukcją jest $< m^2$ — liczby nie puchną niezależnie od $n$. Właśnie policzyłeś ręcznie operację, którą Twój telefon robi przy każdym HTTPS.

Wieża potęg rośnie szybko: ile cyfr ma $2^{1000}$? Oszacuj logarytmem dziesiętnym ($\log_{10} 2 \approx 0{,}301$) — i skomentuj, czemu szybkie potęgowanie liczy tę liczbę bez trudu, choć jej nie przeczytasz do końca życia… przeczytasz?

Wskazówka i odpowiedź

Cyfr jest $\lfloor 1000 \cdot 0{,}301 \rfloor + 1 = 302$. Szybkie potęgowanie wykona ledwie ~10 podniesień do kwadratu (choć na koniec na liczbach kilkusetcyfrowych — Python to łyka). 302 cyfry przeczytasz w minutę — ale już $2^{10^6}$ (301 tysięcy cyfr, ~15 mnożeń więcej!) czytałbyś kilka dni. Koszt algorytmu i rozmiar wyniku to osobne historie — czasem wynik jest droższy od jego policzenia.

🔍 Sprawdź, czy umiesz

Zapisać przepis rekurencyjny szybkiego potęgowania z przypadkiem bazowym.
Prześledzić wersję iteracyjną, wskazując bity wykładnika.
Wyjaśnić, która linijka chroni przed podwójnym liczeniem i co się stanie bez niej.

Ucz się tej jednostki z asystentem