BerechnungsverfahrenEuklidischer Algorithmus | ![]() |
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 Euklid beschrieben.
Der euklidische Algorithmus verwendet ein Iterationsschema, im Folgenden an einem Beispiel dargestellt. Berechnet wird der größte gemeinsame Teiler ggt(a, b) der Zahlen a = 98 und b = 35.
a | b | q | r | |||
---|---|---|---|---|---|---|
98 | : | 35 | = | 2 | Rest | 28 |
35 | : | 28 | = | 1 | Rest | 7 |
28 | : | 7 | = | 4 | Rest | 0 |
7 | : | 0 |
In jedem Iterationsschritt 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 ab gilt. Bei der Berechnung etwa von ggt(35, 98) lautet die erste Zeile des Iterationsschemas
35 | : | 98 | = | 0 | Rest | 35 |
Die weiteren Iterationsschritte 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.
Die Korrektheit des euklidischen Algorithmus beruht auf der Tatsache, dass jeder gemeinsame Teiler d von zwei Zahlen a
0, b
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
0, b
. Dann gilt
ggt(a, b) = ggt(b, a mod b)
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.
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 Programmiersprache Python für die mod-Operation.
Funktion ggt | ||
Eingabe: | Zahlen a, b ![]() ![]() | |
Ausgabe: | Größter gemeinsamer Teiler ggt(a, b) | |
Methode: |
|
Die Rekursion terminiert, da a mod b stets kleiner als b ist; das zweite Argument der Funktion wird also irgendwann 0.
Die ursprüngliche iterative Version ergibt folgendes Programm. In der Programmiersprache Python ist eine gleichzeitige Wertzuweisung eines Tupels von Werten an ein Tupel von Variablen möglich.
Python | Java | |||
|
|
Der euklidische Algorithmus hat logarithmische Zeitkomplexitä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 Voraussetzung b<a gilt
a mod b < a/2
Im Iterationsschema 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.
Aufgabe 1: Programmieren Sie die iterative Version des euklidischen Algorithmus und geben Sie dabei zusätzlich in jedem Schleifendurchlauf 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 beispielsweise in dem iterativen Java-Programm die Anweisung b=r; durch
b=Math.min(r, b-r); |
Geben Sie wieder in jedem Schleifendurchlauf die Werte von a und b aus. Verwenden Sie wieder das Zahlenbeispiel 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)
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.
Weiter mit: [Erweiterter euklidischer Algorithmus] oder
![]() |
![]() |
![]() |
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: