Gamla algoritmer: Vad egyptiska bråk lär oss om modern programmering

Varje gång du skriver en rekursiv funktion eller implementerar en girig algoritm (greedy algorithm) står du på skuldrorna av matematiker som levde för tusentals år sedan. Egyptiska bråk – matematiska uttryck som bara använder reciproka tal av heltal – representerar en av de äldsta dokumenterade algoritmerna i mänsklighetens historia. Och de är betydligt mer sofistikerade än de först verkar.

Problemet som egypterna löste

Vi är vana vid moderna bråk: 3/7, 5/12, 17/23. Men den här notationen blev inte vanlig i Europa förrän på 1700-talet. Innan dess behövde du dela upp bråket i en summa av enhetsbråk – alltså bråk med 1 i täljaren.

Egyptierna stod inför en praktisk utmaning: hur delar man rättvist 7 limpor bröd mellan 8 personer? Svaret var inte att skriva 7/8. Istället bröt de ner det till en summa av distinkta enhetsbråk: 1/2 + 1/4 + 1/8.

Den här till synes enkla metoden krävde sofistikerat matematiskt tänkande och skapade det vi idag kallar för den egyptiska bråkalgoritmen.

Girig algoritm, forntida stil

Här blir det intressant för oss utvecklare. Metoden som egypterna använde för att konvertera vilket bråk som helst till ett egyptiskt bråk är i grunden en greedy algorithm – välj det största möjliga enhetsbråket, subtrahera det, och upprepa.

Ta 4/23. Algoritmen frågar: vilket är det minsta heltal som är större än 23/4? Svaret är 6. Så vi börjar med 1/6, subtraherar det från 4/23, får 1/138, och är klara: 4/23 = 1/6 + 1/138.

Den här metoden fungerar varje gång – bevisad som matematisk sats år 1880, även om europeiska matematiker hade känt till tekniken sedan Fibonacci på 1100-talet.

Varför det här spelar roll för moderna utvecklare

Vid första anblicken verkar det här som historisk kuriosa. Men fundera på vad som faktiskt händer i den algoritmen:

1. Rekursiv dekomposition – Bryt ner ett komplext problem i enklare delproblem
2. Girigt urval – Gör det optimala lokala valet i varje steg
3. Termineringsbevis – Resten blir alltid mindre, vilket garanterar att algoritmen tar slut

De här koncepten utgör grunden för modernt algoritmiskt tänkande. När du skriver en rekursiv funktion applicerar du samma logiska struktur som dessa forntida matematiker använde.

Den historiska luckan

Det finns en obekväm historik här som förtjänar att nämnas. Metoden med egyptiska bråk föregår grekisk matematik med årtusenden. Ändå, när europeiska matematiker "återupptäckte" Rhindpapyrusen på 1800-talet, tillskrevs tekniken ofta grekiska lärda snarare än dess verkliga ursprung i det forntida Egypten.

Det här mönstret – där bidrag från afrikanska och andra icke-europeiska civilisationer minimeras eller raderas från matematikhistorien – lever kvar i hur vi undervisar och diskuterar datavetenskap idag.

Matematiska mysterier

Ett fascinerande pussel involverar det som vissa akademiker kallar för "den egyptiska trippeln": 13, 17 och 173. När det tolkas som 3 + 1/13 + 1/17 + 1/173 approximerar det här uttrycket π till fyra decimaler – mer exakt än det ofta citerade egyptiska värdet 3,16.

Huruvida detta var avsiktligt eller tillfälligt diskuteras fortfarande bland matematikhistoriker.

Från forntid till nutid

Egyptiska bråk hänger ihop med kedjebråk, ett ämne som fortfarande studeras inom datavetenskap och talteori. Den giriga algoritm-approachen har moderna tillämpningar i problem som rör resursallokering, schemaläggning och optimering.

Så nästa gång du felsöker en rekursiv funktion eller förklarar varför en greedy approach fungerar: du deltar i en matematisk tradition som sträcker sig nästan 4 000 år tillbaka i tiden.

Ibland är de äldsta algoritmerna fortfarande de bästa.