stiehler.dev Marian Stiehler
Euklidischer Algorithmus in Swift, Mathematica und MMIX
Der Euklidische Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier Zahlen gehört, weil er so simpel ist, zu den typischen Beispielen der Algorithmenanalyse. Hier sollen drei Implementierungen dieses Algorithmus gezeigt werden, jeweils in algorithmischer Form, in Swift, in Mathematica und teilweise in MMIX.
MMIX ist ein 64-Bit-Modellcomputer (RISC) aus Donald Knuth’s The Art of Computer Programming. Ihn kann man mit einer hardwarenahen Assembler-Sprache programmieren. Das Folgende sind meine Implementierungen des Euklidischen Algorithmus; Knuth selbst stellt auch welche vor.
Die algorithmische Darstellung orientiert sich an der Darstellung von Donald E. Knuth in The Art of Computer Programming.
Triviale Implementierung
algorithmische Form
Gegeben sind zwei positive Ganzzahlen m und n; finde ihren größten gemeinsamen Teiler.
E1. [Finde Rest] Teile m durch n, r sei der Rest.
E2. [Ist Rest 0?] Wenn r = 0 ist, terminiert der Algorithmus. n ist die Lösung.
E3. [Reduziere] Setze m ← n, n ← r und gehe zurück zu Schritt E1. ❙
Mathematica
Da Mathematica die Parameter von Funktionen (hier a, b) wie Konstanten behandelt, müssen ihre Werte Variablen (hier m, n) zugewiesen werden.
Swift
MMIX
Implementierung ohne triviale Ersetzungen
Hier soll es darum gehen, alle trivialen Ersetzungen wie m ← n zu vermeiden und auf die Variable r zu verzichten.
Gegeben sind zwei positive Ganzzahlen m und n; finde ihren größten gemeinsamen Teiler.
F1. [Finde Rest für m mod n] Teile m durch n, m wiederum sei der Rest.
F2. [Ist Rest m 0?] Wenn m = 0 ist, terminiert der Algorithmus. n ist die Lösung.
F3. [Finde Rest für n mod m] Teile n durch m, n wiederum sei der Rest.
F4. [Ist Rest n 0?] Wenn n = 0 ist, terminiert der Algorithmus. m ist die Lösung. Andernfalls gehe zu Schritt F1. ❙
Mathematica
Swift
MMIX
Rekursive Implementierung
Gegeben sind zwei positive Ganzzahlen m und n; finde ihren größten gemeinsamen Teiler.
G1. [Abbruchbedingung: n = 0?] Wenn n = 0 ist, ist m die Lösung.
G2. [Rekursion: G(n, m mod n)] Gehe zu Schritt 1, setze m ← n und n ← m mod n. ❙
Mathematica
Es gibt (mindestens) zwei sinnvolle rekursive Implementierungen dieses Algorithmus: ohne und mit Pattern Matching.