NWD, NWW i ułamki — najstarszy algorytm świata

🎯 Po co Ci to?

Jest rok około 300 p.n.e. Euklides z Aleksandrii zapisuje w „Elementach" przepis na znajdowanie największej wspólnej miary dwóch odcinków. Dziś, 2300 lat później, dokładnie ten przepis wykonuje Twój telefon za każdym razem, gdy skraca ułamek, synchronizuje animacje o różnych okresach albo liczy kryptografię. Żaden inny algorytm nie pracuje nieprzerwanie tak długo. Poznasz go w wersji antycznej (odejmowanie) i nowożytnej (reszta z dzielenia) — a przy okazji raz na zawsze uporządkujesz NWD, NWW i rachunki na ułamkach.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • obliczać NWD algorytmem Euklidesa (przez odejmowanie) i stosować go do skracania ułamków;
  • wyznaczać NWW ze wzoru $\text{NWW}(a,b) = a \cdot b ,/, \text{NWD}(a,b)$ i używać go do wspólnego mianownika;
  • (w rozszerzeniu) zapisać Euklidesa z resztą — iteracyjnie i rekurencyjnie — i wyjaśnić, czemu jest błyskawiczny.

📘 Wyjaśnienie

📐 DEFINICJA — NWD i NWW: największy wspólny dzielnik $\text{NWD}(a,b)$ to największa liczba dzieląca i $a$, i $b$; najmniejsza wspólna wielokrotność $\text{NWW}(a,b)$ to najmniejsza liczba, którą dzielą i $a$, i $b$.

Po ludzku: NWD — największa „wspólna cegiełka" dwóch liczb; NWW — najbliższe „wspólne spotkanie" ich wielokrotności. Czym NIE jest: NWD nie wymaga rozkładu na czynniki pierwsze. Szkolna metoda „rozłóż obie i weź wspólne" działa, ale dla dużych liczb jest beznadziejnie droga (rozkład jest trudny — o tym jeszcze w 4.4 i 5.7). Euklides znajduje NWD, w ogóle nie zaglądając w czynniki.

Pomysł Euklidesa. Opiera się na jednej obserwacji: wspólne dzielniki pary $(a, b)$ i pary $(a - b, b)$ to dokładnie te same liczby (jeśli coś dzieli $a$ i $b$, dzieli też ich różnicę — i odwrotnie). Skoro tak, można większą liczbę zastępować różnicą, w kółko, aż liczby się zrównają — a wtedy odpowiedź stoi przed nami:

def nwd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

Prześledź dla $(84, 36)$: $(48, 36) \to (12, 36) \to (12, 24) \to (12, 12)$ — NWD = 12. Za każdym krokiem para się zmniejsza, a wspólne dzielniki zostają nietknięte; gdy liczby się zrównają, są równe swojemu NWD.

Do czego to? Dwa rachunki, które od dziś robisz algorytmicznie:

  • Skracanie ułamka: $\frac{84}{36}$ — dzielisz licznik i mianownik przez $\text{NWD} = 12$: $\frac{7}{3}$. Ułamek nieskracalny za jednym zamachem, bez zgadywania „przez co jeszcze się dzieli".
  • Wspólny mianownik: do $\frac{5}{12} + \frac{7}{18}$ potrzebujesz $\text{NWW}(12, 18)$. Nie licz go osobno — jest wzór: $\text{NWW}(a,b) = \frac{a \cdot b}{\text{NWD}(a,b)}$, tu $\frac{12 \cdot 18}{6} = 36$. (Intuicja: iloczyn $a \cdot b$ liczy wspólną cegiełkę dwa razy — dzielenie przez NWD zdejmuje duplikat.)

💭 Pomyśl: Prześledź nwd(1000000, 3) wersją z odejmowaniem. Nie do końca — tylko oszacuj, ile kroków to potrwa. Widzisz problem?

Sprawdź odpowiedź

Odejmowanie będzie skubać: $(999997, 3), (999994, 3), \dots$ — ponad 300 tysięcy kroków, po trzy oczka na raz. Dla pary $(10^{18}, 3)$ — wieczność. Antyczna wersja jest poprawna, ale gdy liczby są bardzo różnych rozmiarów, zamienia się w żółwia. Zauważ jednak, że te wszystkie odejmowania robią w kółko jedno i to samo: odejmują $b$, aż się nie da. A „odejmuj $b$, aż się nie da" ma przecież jednoinstrukcyjną nazwę…

[R] Euklides z resztą. „Odejmuj $b$ od $a$, aż zostanie mniej niż $b$" to dokładnie reszta z dzielenia: $a \bmod b$. Cała seria odejmowań zwija się w jedną operację:

def nwd(a, b):
    while b != 0:
        a, b = b, a % b        # para (a, b) → (b, reszta)
    return a

(Zapis a, b = b, a % b podmienia obie zmienne naraz — prawa strona liczy się w całości przed przypisaniem, więc stare wartości nie giną w połowie operacji.)

Prześledź $(1071, 462)$: reszta $1071 \bmod 462 = 147$, więc $(462, 147)$; dalej $462 \bmod 147 = 21$, więc $(147, 21)$; dalej $147 \bmod 21 = 0$, więc $(21, 0)$ — NWD = 21. Trzy obroty. Wersja z odejmowaniem potrzebowałaby jedenastu, a dla niewdzięcznych par — milionów.

Jak szybki jest Euklides z resztą? Da się pokazać, że co dwa obroty pętli większa liczba maleje przynajmniej o połowę — a „o połowę na (dwa) kroki" to melodia, którą znasz z jednostki 2.7: koszt logarytmiczny. NWD liczb osiemnastocyfrowych to około stu obrotów. Dlatego właśnie ta wersja pracuje w bibliotekach kryptograficznych na liczbach po 600 cyfr — i nawet nie zipnie.

Wersja rekurencyjna. Obserwację „$\text{NWD}(a, b) = \text{NWD}(b, a \bmod b)$, a $\text{NWD}(a, 0) = a$" można zapisać jeszcze zwięźlej — jako funkcję, która wywołuje samą siebie:

def nwd(a, b):
    if b == 0:
        return a               # przypadek bazowy: koniec schodów
    return nwd(b, a % b)       # ten sam problem, mniejsze liczby

To Twoje pierwsze spotkanie z rekurencją w kodzie — funkcja nwd woła nwd! Nie ma tu magii: każde wywołanie dostaje mniejszą parę, a łańcuszek kończy się na b == 0. Porównaj obie wersje: robią identyczne kroki, różnią się tylko szatą — pętla kontra samowywołanie. Pełną teorię rekurencji (i odpowiedź, kiedy która szata jest lepsza) dostaniesz w dziale 7; na razie zapamiętaj Euklidesa jako wzorcowy przykład, że rekurencja bywa najkrótszym zapisem pomysłu.

🐞 Znajdź błąd

Kolega liczy NWW tak: def nww(a, b): return a * b / nwd(a, b). Dla $(12, 18)$ dostaje 36.0 — działa? Wskaż dwie usterki (jedną kosmetyczną, jedną głębszą).

Sprawdź odpowiedź

Kosmetyczna: / w Pythonie zawsze daje ułamek (36.0, nie 36) — NWW jest z definicji całkowite, więc należy dzielić całkowicie: a * b // nwd(a, b) (operator //). Głębsza: kolejność działań. a * b dla wielkich liczb tworzy gigantyczny iloczyn tylko po to, żeby zaraz go podzielić — lepiej a // nwd(a, b) * b: najpierw zmniejsz, potem mnóż. W Pythonie duże liczby „tylko" spowalniają, ale w większości języków iloczyn przekroczyłby zakres typu i przekręcił się (przepełnienie z 2.3!) — cichy, fałszywy wynik. Kolejność operacji bywa treścią algorytmu.

🕰️ Skąd to wiemy

„Elementy" Euklidesa to najdłużej używany podręcznik w historii ludzkości — algorytm NWD siedzi w Księdze VII jako sposób na wspólną miarę odcinków (Grecy myśleli geometrycznie: odkładali krótszy odcinek na dłuższym, czyli… odejmowali). Donald Knuth, autor biblii informatyków „The Art of Computer Programming", nazwał go „dziadkiem wszystkich algorytmów, bo jest najstarszym nietrywialnym algorytmem, który przetrwał do dziś". Masz właśnie w rękach kawałek najdłużej działającej technologii świata.

🛠️ Teraz Ty

Bez komputera: policz Euklidesem (obiema wersjami, jeśli robisz rozszerzenie) $\text{NWD}(252, 198)$ i skróć ułamek $\frac{198}{252}$; potem $\text{NWW}(15, 40)$ i policz $\frac{7}{15} + \frac{9}{40}$. Z komputerem: napisz program, który wczytuje dwa ułamki (cztery liczby) i wypisuje ich sumę w postaci nieskracalnej — komplet dzisiejszej jednostki w jednym programie.

📐 Definicje tej lekcji

  • Algorytm Euklidesa — NWD przez powtarzane zastępowanie: większej liczby różnicą (wersja antyczna) lub pary $(a,b)$ parą $(b, a \bmod b)$ (wersja z resztą, [R]).
  • Wzór na NWW — $\text{NWW}(a,b) = a \cdot b / \text{NWD}(a,b)$; w kodzie z dzieleniem całkowitym i mnożeniem po dzieleniu.

📌 Najważniejsze w pigułce

  • Euklides znajduje NWD bez rozkładu na czynniki — i dlatego działa także tam, gdzie rozkład jest nieosiągalny.
  • NWD → skracanie ułamków; NWW z wzoru → wspólny mianownik; obie operacje jednym algorytmem.
  • [R] Wersja z resztą jest logarytmiczna: sto obrotów wystarcza na liczby osiemnastocyfrowe; zapis rekurencyjny to trzy linijki.

🎒 Zadania

  1. Policz $\text{NWD}(144, 89)$ (rozszerzenie: wersją z resztą, notując pary). Co ciekawego widzisz w kolejnych resztach?
Wskazówka i odpowiedź

$(144, 89) \to (89, 55) \to (55, 34) \to (34, 21) \to (21, 13) \to (13, 8) \to (8, 5) \to (5, 3) \to (3, 2) \to (2, 1) \to (1, 0)$: NWD = 1 (liczby względnie pierwsze). Reszty to… ciąg Fibonacciego wstecz! To nie przypadek: sąsiednie liczby Fibonacciego są najgorszym możliwym wejściem dla Euklidesa (najwolniej maleją) — i wyznaczają jego maksymalną liczbę kroków. Spotkanie z Fibonaccim tuż przed jednostką o Fibonaccim to dobra wróżba.

  1. Trzy autobusy odjeżdżają z pętli o 6:00, a potem co 12, 18 i 30 minut. O której znów odjadą razem? Rozwiąż przez NWW (dwustopniowo) i zapisz plan obliczeń.
Wskazówka i odpowiedź

$\text{NWW}(12, 18) = \frac{12 \cdot 18}{6} = 36$; $\text{NWW}(36, 30) = \frac{36 \cdot 30}{6} = 180$. Razem co 180 minut: o 9:00. NWW trzech liczb liczy się łańcuchowo — $\text{NWW}(a, b, c) = \text{NWW}(\text{NWW}(a,b), c)$ — bo „wspólne spotkanie trzech" to „wspólne spotkanie spotkania dwóch z trzecim".

  1. [R] Ile obrotów wykona pętla while b != 0 dla pary $(10^{18}, 7)$? Odpowiedz bez śledzenia — jednym argumentem.
Wskazówka i odpowiedź

Pierwszy obrót: $(7, 10^{18} \bmod 7)$ — po jednym kroku obie liczby są już maleńkie (co najwyżej 6)! Dalej najwyżej kilka obrotów. Porównaj z wersją odejmowania: $\sim 10^{17}$ kroków. Reszta z dzielenia „przeskakuje" wszystkie odejmowania naraz — dlatego rozmiar mniejszej liczby, nie większej, rządzi kosztem Euklidesa.

🔍 Sprawdź, czy umiesz

  • Wyjaśnić, dlaczego para $(a, b)$ i para $(a-b, b)$ mają te same wspólne dzielniki.
  • Skrócić ułamek i znaleźć wspólny mianownik, używając NWD/NWW świadomie.
  • [R] Napisać Euklidesa z resztą z pamięci — w wersji z pętlą i rekurencyjnej.

Ucz się tej jednostki z asystentem