noun_20527_58c6c2.png

Marian Stiehler

Student

Informatik
Philosophie Psychologie Kunstwissenschaft

Euklidischer Algorithmus in Swift und Mathematica

Euklidischer Algorithmus in Swift und Mathematica

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 und in Mathematica.

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.
mGCD1[a_Integer, b_Integer] :=
 {m = a; n = b; r = Mod[m, n];
   While[r != 0,
    m = n; n = r; 
    r = Mod[m, n]];
   n}[[1]]
     
mGCD1[6099,2166]

Swift

var n = 2166
var m = 6099

var r = m % n

while r != 0 {
    m = n
    n = r
    r = m % n
}

print("The GCD is", n)

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

mGCD2[a_Integer, b_Integer] :=
 {
   m = a; n = b;
   Catch[
    While[True,
     m = Mod[m, n];
     If[m == 0, Throw[n]];
     n = Mod[n, m];
     If[n == 0, Throw[m]]
     ]
    ]
   }[[1]]
     
mGCD2[6099,2166]

Swift

var n = 2166
var m = 6099

while n != 0 {
    m = m % n
    if m == 0 {
        m = n
        break
    }
    n = n % m
}

print("The GCD is", n)

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.

mGCDR[m_Integer, n_Integer] :=
 {If[n == 0, m, mGCDR[n, Mod[m, n]]]}[[1]]
  
mGCDR[6099, 2166]
  
mGCDRR[m_Integer, n_Integer /; n == 0] = m
mGCDRR[m_Integer, n_Integer] := mGCDRR[n, Mod[m, n]]

mGCDRR[6099, 2166]

Swift

func mGCDR (m: Int, n: Int) {
    if n == 0 {
        print("The GCD is", m)
    } else {
        mGCDR(m: n, n: m % n)
    }
}

mGCDR(m: 6099, n: 2166)
Ein Primzahl-Algorithmus in Swift: iterativ, objektorientiert und rekursiv

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

Brücken in Deutschland

Brücken in Deutschland