Starożytne algorytmy: Czego ułamki egipskie uczą nas o programowaniu

Ilekroć piszesz funkcję rekurencyjną lub implementujesz algorytm zachłanny, podążasz śladami matematyków sprzed tysięcy lat. Ułamki egipskie to jeden z najstarszych udokumentowanych algorytmów w historii ludzkości. I są znacznie bardziej wyrafinowane, niż mogłoby się wydawać na pierwszy rzut oka.

Problem, który rozwiązali Egipcjanie

Współczesny zapis ułamków wydaje się nam naturalny: 3/7, 5/12, 17/23. Ale ta notacja nie była powszechna w Europie aż do XVIII wieku. Wcześniej, jeśli chciałeś zapisać ułamek, musiałeś rozłożyć go na sumę ułamków jednostkowych – czyli takich, gdzie w liczniku stoi jedynka.

Egipcjanie stanęli przed praktycznym wyzwaniem: jak uczciwie podzielić 7 bochenków chleba między 8 osób? Odpowiedź nie była prosta – nie wystarczyło napisać 7/8. Zamiast tego rozbijali to na sumę różnych ułamków jednostkowych: 1/2 + 1/4 + 1/8.

To pozornie proste podejście wymagało wyrafinowanego myślenia matematycznego i dało początek temu, co dziś nazywamy algorytmem ułamków egipskich.

Algorytm zachłanny w starożytnym wydaniu

Tu robi się ciekawie dla programistów. Metoda, której Egipcjanie używali do zamiany dowolnego ułamka na ułamek egipski, to w gruncie rzeczy algorytm zachłanny – wybierz największy możliwy ułamek jednostkowy, odejmij go, a potem powtarzaj.

Weźmy 4/23. Algorytm pyta: jaka jest najmniejsza liczba całkowita większa od 23/4? To 6. Więc zaczynamy od 1/6, odejmujemy od 4/23, otrzymujemy 1/138 i gotowe: 4/23 = 1/6 + 1/138.

To podejście działa zawsze – twierdzenie matematyczne udowodnione w 1880 roku, choć Europejczycy znali tę technikę już od Fibonacciego w XII wieku.

Dlaczego to ma znaczenie dla współczesnych programistów

Na pierwszy rzut oka może to wyglądać jak ciekawostka historyczna. Ale przyjrzyjmy się, co dokładnie dzieje się w tym algorytmie:

1. Dekompozycja rekurencyjna – rozbijamy złożony problem na prostsze podproblemy
2. Wybór zachłanny – podejmujemy optymalną decyzję lokalną na każdym kroku
3. Dowód zakończenia – reszta stale się zmniejsza, co gwarantuje zakończenie

Te koncepcje leżą u podstaw nowoczesnego myślenia algorytmicznego. Kiedy piszesz rekursywną funkcję, stosujesz tę samą strukturę logiczną, którą wykorzystywali starożytni matematycy.

Luka w historii

Warto wspomnieć o pewnej niewygodnej historii. Metoda ułamków egipskich powstała na długo przed grecką matematyką. A jednak gdy europejscy matematycy „na nowo odkryli" Papirus Rhinda w XIX wieku, technikę tę często przypisywano greckim uczonym zamiast jej prawdziwym twórcom ze starożytnego Egiptu.

Ten wzorzec – marginalizowanie wkładu cywilizacji afrykańskich i innych pozaeuropejskich w rozwój matematyki – niestety utrzymuje się do dziś w sposobie, w jaki nauczamy i omawiamy informatykę.

Matematyczne zagadki

Jedną z fascynujących łamigłówek jest to, co niektórzy badacze nazywają „trójką egipską": 13, 17 i 173. Kiedy zinterpretujemy to jako 3 + 1/13 + 1/17 + 1/173, otrzymamy przybliżenie liczby π z dokładnością do czterech miejsc po przecinku – dokładniejsze niż powszechnie podawana egipska wartość 3,16.

Czy było to zamierzone, czy też czysty przypadek – historycy matematyki wciąż się spierają.

Od starożytności do współczesności

Ułamki egipskie łączą się z ułamkami łańcuchowymi, tematem wciąż żywo obecnym w informatyce i teorii liczb. Podejście oparte na algorytmie zachłannym ma dziś zastosowanie w problemach alokacji zasobów, planowania i optymalizacji.

Więc następnym razem, gdy debugujesz rekursywną funkcję lub tłumaczysz, dlaczego działa podejście zachłanne, pamiętaj: uczestniczysz w tradycji matematycznej sięgającej prawie 4000 lat wstecz.

Czasem najstarsze algorytmy są wciąż najlepsze.