Euklidischer Algorithmus
Der euklidische Algorithmus ist ein Verfahren zur Bestimmung des größten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen a und b. Es ist einer der ältesten bekannten Algorithmen der Welt, benannt nach dem griechischen Mathematiker Euklid, der ihn um 300 v. Chr in seinem Werk Die Elemente angegeben hat. Das Verfahren war jedoch schon früher bekannt. Euklid nannte es antenaresis. Der Algorithmus kommt ohne die Kenntnis der Primfaktorzerlegung der Zahlen a und b aus.
Table of contents |
2 Beispiel 3 Der binäre euklidische Algorithmus 4 Laufzeitanalyse 5 Euklidischer Algorithmus und Kettenbruchzerlegung 6 Erweiterung 7 Siehe auch |
Wie im Zitat oben angegeben formulierte Euklid das Problem seinerzeit geometrisch, er suchte nach einem gemeinsamen "Maß" für die Längen zweier Linien. Euklid löste das Problem, indem er wiederholt die kleinere der beiden Längen von der größeren abzog.
Ist die Differenz von a und b sehr groß, sind unter Umständen sehr viele Subtraktionsschritte notwendig. Heutzutage werden die Schritte 2 und 3 deshalb in der Regel dadurch ersetzt, dass man, an Stelle der Differenz von m und n, für r den Rest bei der Division von m durch n nimmt.
Ein weiterer Vorteil dieser Variante ist, dass man sie auf beliebige euklidische Ringe (zum Beispiel Polynomringe, siehe Ringtheorie) übertragen kann, in denen der klassische Algorithmus nicht funktioniert.Der klassische Algorithmus
Das Prinzip des euklidischen Algorithmus wird auch gegenseitige Wechselwegnahme genannt. Eingangsgrößen sind zwei natürliche Zahlen a und b. Bei der Berechnung verfährt man nach Euklid wie folgt:
Nach Ablauf des Verfahrens hat man mit m den ggT von a und b gefunden.
m | n | r |
---|---|---|
1071 | 1029 | 42 |
1029 | 42 | 21 |
42 | 21 | 0 |
21 | 0 |
Der ggT ist damit 21.
Ein Problem bei der Umsetzung des euklidischen Algorithmus auf Computer ist Division, die unter Umständen einen hohen Rechenaufwand bedeutet. Hier ist deshalb der binäre euklidische Algorithmus besonders geeignet. Er verwendet nur Subtraktion und die im Binärsystem besonders einfach durchzuführende Division durch 2.
Hinter dem binären euklidischen Algorithmus steckt die Tatsache, dass 2 kein Faktor des ggT zweier Zahlen sein kann, wenn mindestens eine der beiden ungerade ist. Aus einer geraden Zahl kann man also so lange 2 ausdividieren, bis diese ungerade wird.
Dies geschieht in Schritt 3. Wenn im Schritt 5 von einer ungeraden Zahl eine ungerade Zahl abgezogen wird — was immer der Fall ist —, ist das Ergebnis eine gerade Zahl, aus der man nun wieder 2 ausdividieren kann. Die Bitlänge der Restzahlen verringert sich so kontinuierlich.
Das einzige Problem ergibt sich bei der Eingabe zweier gerader Zahlen. Hier muss man im Voraus entsprechend oft 2 ausdivieren (Schritt 2). Die Zahl der Divisionen muss man sich merken, da diese nach Beendigung des Algorithmus wieder rückgängig gemacht werden müssen.
Mit dem euklidischen Algorithmus kann man den ggT mit verhältnismäßig geringem Aufwand (im Vergleich zur Berechnung der Primfaktorzerlegung der Zahlen a und b) berechnen. Bei der Laufzeitanalyse stellt sich interessanterweise heraus, dass der schlimmste Eingabefall zwei aufeinander folgende Fibonacci-Zahlen sind. Die Laufzeit beträgt im schlimmsten Fall Θ(n), wobei n die Anzahl der Ziffern in der Eingabe ist (siehe Landau-Symbole).
Allerdings ist die Division beliebig großer Zahlen nicht O(1), also ist die tatsächliche Laufzeit O(n²).
Die Quotienten, die im euklidischen Algorithmus vorkommen, sind gerade die Zahlen, die in der Kettenbruchzerlegung von a/b vorkommen. Hier für das obige Beispiel mit hervorgehobenen Ziffern:
Merkt man sich die Quotienten bei der Berechnung, so lässt sich damit eine Darstellung sa+tb=ggT(a,b) mit ganzen Zahlen s und t finden. Dies nennt man den erweiterten euklidischen Algorithmus. Damit lassen sich die Inversen in Restklassenringen berechnen.
Eine andere Erweiterung ist der Algorithmus, der hinter dem Quadratischen Reziprozitätsgesetz steckt. Damit lässt sich das Jacobi-Symbol effizient berechnen.
Der binäre euklidische Algorithmus
Nach Ablauf erhält man ggT(a,b) = n·2k.Laufzeitanalyse
Euklidischer Algorithmus und Kettenbruchzerlegung
Hieraus kann man ablesen, dass
Dieses Verfahren lässt sich auch für jede beliebige reelle Zahl r anwenden. Ist r nicht rational, so endet der Algorithmus einfach nie. Die so gewonnene Folge an Quotienten stellt dann die unendliche Kettenbruchzerlegung von r dar.Erweiterung
Siehe auch
kgV und ggT, Computerprogramm