| |
|
| Table of contents |
|
2 Beispiel 3 Der binäre Euklidische Algorithmus 4 Laufzeitanalyse 5 Euklidischer Algorithmus und Kettenbruchzerlegung 6 Erweiterung |
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.
Möchte man die den ggT von 1071 und 1029 berechnen, so erhält man der Reihe nach für m, n und r:
{| border="1"
! m !! n !! r
|-----
| align="right" | 1071 || align=right | 1029 || align="right" | 42
|-----
| align="right" | 1029 || align=right | 42 || align="right" | 21
|-----
| align="right" | 42 || align=right | 21 || align="right" | 0
|-----
| align="right" | 21 || align=right | 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.
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).
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.
siehe auch: kgV und ggT
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.Beispiel
Der binäre Euklidische Algorithmus
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.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