noun_20527_58c6c2.png

Marian Stiehler

Student

Informatik
Philosophie Psychologie Kunstwissenschaft

Euklidischer Algorithmus in Swift, Mathematica und MMIX

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 mn, nr 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 mn 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 mn und nm mod n. ❙

Mathematica

Es gibt (mindestens) zwei sinnvolle rekursive Implementierungen dieses Algorithmus: ohne und mit Pattern Matching.

Swift

Ein Primzahl-Algorithmus in Swift, C++ und MMIX: iterativ, objektorientiert und rekursiv

Ein Primzahl-Algorithmus in Swift, C++ und MMIX: iterativ, objektorientiert und rekursiv

Mein Sicherheits-Toolkit

Mein Sicherheits-Toolkit