Vanhat algoritmit: mitä egyptiläiset murtoluvut opettavat ohjelmoinnista

Joka kerta kun kirjoitat rekursiivisen funktion tai toteutat ahneen algoritmin, astut jälkiin, jotka matemaatikot jättivät tuhansia vuosia sitten. Egyptiläiset murtoluvut – matemaattiset ilmaisut, joissa käytetään vain kokonaislukujen käänteislukuja – edustavat yhtä ihmiskunnan vanhimmista dokumentoituista algoritmeista. Ja ne ovat paljon hienostuneempia kuin miltä ne ensi silmäyksellä vaikuttavat.

Ongelma, jonka egyptiläiset ratkaisivat

Nykyajan murtoluvut tuntuvat luonnollisilta: 3/7, 5/12, 17/23. Mutta tämä merkintätapa yleistyi Euroopassa vasta 1700-luvulla. Sitä ennen murtoluvut piti ilmaista yksikkömurtolukujen summina – eli murtolukuina, joiden osoittaja on aina yksi.

Egyptiläisten käytännön haaste oli tällainen: miten jaat oikeudenmukaisesti seitsemän leipää kahdeksalle henkilölle? Vastaus ei ollut yksinkertaisesti 7/8. Sen sijaan he ilmaisivat sen erilaisten yksikkömurtolukujen summana: 1/2 + 1/4 + 1/8.

Tämä näennäisen yksinkertainen lähestymistapa vaati kehittynyttä matemaattista ajattelua ja loi sen, mitä nykyään kutsutaan egyptiläiseksi murtolukualgoritmiksi.

Ahne algoritmi antiikin tyyliin

Tässä kohtaa asia muuttuu kiinnostavaksi kehittäjille. Metodi, jolla egyptiläiset muunsivat minkä tahansa murtoluvun egyptiläiseksi murtoluvuksi, on pohjimmiltaan ahne algoritmi – valitse suurin mahdollinen yksikkömurtoluku, vähennä se ja toista.

Ota vaikka 4/23. Algoritmi kysyy: mikä on pienin kokonaisluku, joka on suurempi kuin 23/4? Se on 6. Joten alamme 1/6:sta, vähennämme sen 4/23:sta, saamme 1/138:n, ja olemme valmiita: 4/23 = 1/6 + 1/138.

Tämä lähestymistapa toimii aina – matemaattinen teoreema todistettiin vuonna 1880, vaikka eurooppalaiset olivat tunteneet tekniikan jo 1100-luvulta lähtien Fibonacci-hakutehtävän ansiosta.

Miksi tämä kiinnostaa nykyohjelmoijia

Pinnallisesti tarkasteltuna tämä vaikuttaa vain historialliselta kuriositeetilta. Mutta mieti, mitä tuon algoritmin sisällä tapahtuu:

1. Rekursiivinen hajotus – Pilko monimutkainen ongelma yksinkertaisempaan aliongelmaan
2. Ahne valinta – Tee optimaalinen paikallinen valinta jokaisessa vaiheessa
3. Lopetusehto – Jäännös pienenee aina, mikä takaa valmistumisen

Nämä käsitteet muodostavat modernin algoritmisen ajattelun perustan. Kun kirjoitat rekursiivisen funktion, sovellat samaa loogista rakennetta, jota muinaiset matemaatikot käyttivät.

Historiallinen aukko

Tässä on epämukava historianäkökulma, joka kannattaa noteerata. Egyptiläinen murtolukumetodi on tuhansia vuosia vanhempi kuin kreikkalainen matematiikka. Silti kun eurooppalaiset matemaatikot "uudelleenlöysivät" Rhindin papyruksen 1800-luvulla, tekniikka kiirehdittiin usein attribuoimaan kreikkalaisille oppineille sen todellisen egyptiläisen alkuperän sijaan.

Tämä kaava – jossa afrikkalaisten ja muiden ei-eurooppalaisten sivilisaatioiden panoksia vähätellään tai pyyhkiään pois matematiikan historiasta – elää yhä siinä, miten opetamme ja keskustelemme tietojenkäsittelytieteestä.

Matemaattisia mysteerejä

Yksi kiehtova puzzi liittyy siihen, mitä jotkut tutkijat kutsuvat "egyptiläiseksi kolmikoksi": 13, 17 ja 173. Kun ne tulkitaan muodossa 3 + 1/13 + 1/17 + 1/173, tämä lauseke approksimoi π:tä neljän desimaalin tarkkuudella – tarkemmin kuin yleisesti citeerattu egyptiläinen arvo 3.16.

Oliko tämä tarkoituksellista vai sattumaa, on yhä kiistanalaista historioitsijoiden keskuudessa.

Muinaisesta nykypäivään

Egyptiläiset murtoluvut linkittyvät jatkuviin murtolukuihin, aiheeseen jota edelleen tutkitaan tietojenkäsittelytieteessä ja lukuteoriassa. Ahneen algoritmin lähestymistavalla on moderniakin käyttöä ongelmissa, jotka koskevat resurssien jakamista, aikataulutusta ja optimointia.

Joten kun seuraavan kerran debuggaat rekursiivista funktiota tai selität, miksi ahne lähestymistapa toimii, muista: osallistut matemaattiseen perinteeseen, joka ulottuu lähes 4 000 vuoden taakse.

Joskus vanhimmat algoritmit ovat yhä parhaimmistoa.