Berechnungsverfahren

Euklidischer Algorithmus

 aufwärts

Der euklidische Algorithmus berechnet den größten gemeinsamen Teiler ggt(a, b) von zwei ganzen Zahlen a und b. Der Algorithmus wurde bereits ca. 300 v.Chr. von Euklidzur Person beschrieben.

Euklidischer Algorithmus

Der euklidische Algorithmus verwendet ein Iterations­schema, im Folgenden an einem Beispiel dargestellt. Berechnet wird der größte gemeinsame Teiler ggt(a, b) der Zahlen a = 98 und b = 35.

abqr
98 : 35 = 2 Rest 28
35:28=1Rest7
28:7=4Rest0
7:0

In jedem Iterations­schritt erhält a den Wert von b aus der vorherigen Zeile sowie b den Wert von r aus der vorherigen Zeile. Die Iteration endet, wenn b = 0 gilt. Das entsprechende a ist dann das Ergebnis, also der größte gemeinsame Teiler (im obigen Beispiel die 7).

Es ist nicht erforderlich, dass zu Anfang a größer gleich b gilt. Bei der Berechnung etwa von ggt(35, 98) lautet die erste Zeile des Iterations­schemas

35 : 98 = 0 Rest 35

Die weiteren Iterations­schritte sind dann dieselben wie bei ggt(98, 35), d.h. in der ersten Zeile werden die Zahlen automatisch vertauscht, wenn sie in falscher Reihenfolge stehen.

Korrektheit

Die Korrektheit des euklidischen Algorithmus beruht auf der Tatsache, dass jeder gemeinsame Teiler d von zwei Zahlen a Element natürliche Zahlen0, b Element natürliche Zahlen auch deren Differenz a – b teilt. Damit teilt d auch r = a mod b = a – q·b  mit  q = a div b (ganzzahlige Division). Umgekehrt gilt ebenso, dass jeder gemeinsame Teiler von b und a – q·b auch a teilt.

Damit gilt dies auch für den größten gemeinsamen Teiler von a und b, d.h. es gilt der folgende Satz.

Satz:  Seien a Element natürliche Zahlen0, b Element natürliche Zahlen. Dann gilt

ggt(a, b)  =  ggt(b, a mod b)

Beweis:  Beweis zeigen

In obigem Rechenschema ist somit der größte gemeinsame Teiler der jeweiligen Werte von a und b in jeder Zeile gleich. Da ggt(a, 0) = a gilt, offenbart sich der Wert des größten gemeinsamen Teilers in der letzten Zeile, wenn b = 0 gilt.

Programm

Die Gleichung des obigen Satzes lässt sich unmittelbar für folgende rekursive Version des euklidischen Algorithmus verwenden. Ist b = 0, so liefert die Funktion das korrekte Ergebnis ggt(a, 0) = a (und insbesondere auch ggt(0, 0) = 0). Ansonsten ruft sich die Funktion rekursiv selber mit den Argumenten b und a mod b auf. Das Zeichen % steht in der Programmier­sprache Python für die mod-Operation.

 

Funktion ggt
Eingabe:Zahlen a, b Element natürliche Zahlen0
Ausgabe:Größter gemeinsamer Teiler ggt(a, b)
Methode:
def ggt(a, b):
    if b==0:
        return a
    else:
        return ggt(b, a%b)

 

Die Rekursion terminiert, da a mod b stets kleiner als b ist; das zweite Argument der Funktion wird also irgendwann 0.

Iterative Version

Die ursprüng­liche iterative Version ergibt folgendes Programm. In der Programmier­sprache Python ist eine gleich­zeitige Wert­zuweisung eines Tupels von Werten an ein Tupel von Variablen möglich.

 Python  Java
def ggt(a, b):
    while b!=0:
        a, b = b, a%b
    return a
 
int ggt(int a, int b)
{
    int r;
    while (b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}

Zeitkomplexität

Der euklidische Algorithmus hat logarithmische Zeit­komplexität bezogen auf die Größe der Zahlen a bzw. b.

Der schlechteste Fall für die Anzahl der Schritte des euklidischen Algorithmus tritt ein, wenn a und b zwei aufeinander folgende Fibonacci-Zahlen sind. Bei Eingabe der n+1-ten und der n-ten Fibonacci-Zahl benötigt der euklidische Algorithmus n Schritte. Dies sind nur logarithmisch viele Schritte in Bezug auf die Größe der n-ten Fibonacci-Zahl, denn die Fibonacci-Zahlen steigen exponentiell an.

Eine andere Abschätzung beruht darauf, dass unter der Voraus­setzung b<a gilt

a mod b < a/2

Im Iterations­schema erscheint der Wert a mod b im übernächsten Schritt an der Position von a. Der Wert an der Position von a halbiert sich also mindestens alle zwei Schritte. Damit endet die Iteration nach spätestens 2·log(a) Schritten.

Aufgaben

Aufgabe 1:  Programmieren Sie die iterative Version des euklidischen Algorithmus und geben Sie dabei zusätzlich in jedem Schleifen­durchlauf die Werte von a und b aus. Testen Sie Ihr Programm mit den aufeinander folgenden Fibonacci-Zahlen a=987 und b=610.

Aufgabe 2:  Sie beschleunigen den euklidischen Algorithmus maximal um den Faktor 2, indem Sie anstelle des Restes r das Minimum von r und b-r verwenden.

Ersetzen Sie also beispiels­weise in dem iterativen Java-Programm die Anweisung b=r; durch

b=Math.min(r, b-r);

Geben Sie wieder in jedem Schleifen­durchlauf die Werte von a und b aus. Verwenden Sie wieder das Zahlen­beispiel a=987 und b=610.

Lösen Sie die nächste Aufgabe und überzeugen Sie sich von der Korrektheit dieser Optimierung.

Aufgabe 3:  Modifzieren Sie den oben angegebenen Beweis der Korrektheit des euklidischen Algorithmus und zeigen Sie

ggt(a, b)   =   ggt(b, b – a mod b)

 

Steinscher Algorithmus

Interessant ist auch eine Variante des euklidischen Algorithmus, der steinsche Algorithmus. Der steinsche Algorithmus kommt ohne die relativ aufwendige mod-Operation aus und verwendet nur Bit-Schiebe-Operationen.

Literatur

[CLRS 01]T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. 2. Auflage, The MIT Press (2001)
[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Den euklidischen Algorithmus und andere zahlentheoretische Algorithmen finden Sie auch in meinem Buch.
Weitere(vertikaler Abstand) Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  
[Lan 18]H.W. Lang: Kryptografie für Dummies. Wiley (2018)

Und natürlich finden Sie den euklidischen Algorithmus und andere zahlentheoretische Algorithmen, die in der Kryptografie gebraucht werden, auch in meinem Kryptografie-Buch.

[Weitere Informationen]

Buch  

 

Weiter mit:   [Erweiterter euklidischer Algorithmus]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 12.02.2001   Updated: 26.08.2021
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

 

 

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik