Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDienstag, 15. Oktober 2019 

Euklidischer Algorithmus


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
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 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 früher bekannt. Euklid nannte es antenaresis . Der Algorithmus kommt ohne die Kenntnis Primfaktorzerlegung der Zahlen a und b aus.

Inhaltsverzeichnis

Der klassische Algorithmus

Wenn CD aber AB nicht mißt und nimmt bei AB CD abwechselnd immer das vom größeren weg dann muß (schließlich) eine übrig bleiben die die vorangehende mißt.
(Aus Euklid Die Elemente Herausgegeben von Clemens Wissenschaftliche Buchgesellschaft Darmstadt VII Buch §2)

Das Prinzip des Euklidischen Algorithmus wird gegenseitige Wechselwegnahme genannt. Eingangsgrößen sind zwei natürliche Zahlen a und b . Bei der Berechnung verfährt man nach wie folgt:

  1. setze m = a ; n = b
  2. ist m < n so vertausche m und n
  3. berechne r = m - n
  4. setze m = n n = r
  5. ist r ≠ 0 fahre fort mit Schritt
Nach Ablauf des Verfahrens hat man m den ggT von a und b gefunden.

Wie im Zitat oben angegeben formulierte das Problem seinerzeit geometrisch er suchte nach gemeinsamen "Maß" für die Längen zweier Linien. löste das Problem indem er wiederholt die der beiden Längen von der größeren abzog. die Differenz von a und b sehr groß sind unter Umständen sehr Subtraktionsschritte notwendig. Heutzutage werden die Schritte 2 3 deshalb in der Regel dadurch ersetzt 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 dass man sie auf beliebige euklidische Ringe (zum Beispiel Polynomringe siehe Ringtheorie ) übertragen kann in denen der klassische nicht funktioniert.

Beispiel

Möchte man die den ggT von und 1029 berechnen so erhält man der nach für m n und r :
m n r
1071 1029 42
1029 42 21
42 21 0
21 0

Der ggT ist damit 21.

Der binäre Euklidische Algorithmus

Ein Problem bei der Umsetzung des Algorithmus auf Computer ist Division die unter einen hohen Rechenaufwand bedeutet. Hier ist deshalb binäre euklidische Algorithmus besonders geeignet. Er verwendet nur Subtraktion die im Binärsystem besonders einfach durchzuführende Division durch 2.

  1. setze m = a ; n = b
  2. dividiere m und n durch 2 solange bis eine der Zahlen ungerade ist. Die Zahl der notwendigen sei k . Falls n gerade ist vertausche m und n .
  3. dividiere m durch 2 bis m ungerade ist
  4. ist m < n so vertausche diese Zahlen
  5. setze m = m - n
  6. ist m ≠ 0 dann fahre fort mit 3.
Nach Ablauf erhält man ggT( a b ) = n ·2 k .

Hinter dem binären euklidischen Algorithmus steckt Tatsache dass 2 kein Faktor des ggT Zahlen sein kann wenn mindestens eine der ungerade ist. Aus einer geraden Zahl kann also so lange 2 ausdividieren bis diese wird. Dies geschieht in Schritt 3. Wenn Schritt 5 von einer ungeraden Zahl eine Zahl abgezogen wird — was immer der ist — ist das Ergebnis eine gerade aus der man nun wieder 2 ausdividieren Die Bitlänge der Restzahlen verringert sich so

Das einzige Problem ergibt sich bei Eingabe zweier gerader Zahlen. Hier muss man Voraus entsprechend oft 2 ausdivieren (Schritt 2). Zahl der Divisionen muss man sich merken diese nach Beendigung des Algorithmus wieder rückgängig werden müssen.

Laufzeitanalyse

Mit dem Euklidischen Algorithmus kann man ggT mit verhältnismäßig geringem Aufwand (im Vergleich Berechnung der Primfaktorzerlegung der Zahlen a und  b ) berechnen. Bei der Laufzeitanalyse stellt sich heraus dass der schlimmste Eingabefall zwei aufeinander Fibonacci-Zahlen sind. Die Laufzeit beträgt im schlimmsten Θ( n ) wobei n die Anzahl der Ziffern in der ist (siehe Landau-Symbole ).

Euklidischer Algorithmus und Kettenbruchzerlegung

Die Quotienten die im Euklidischen Algorithmus sind gerade die Zahlen die in der Kettenbruchzerlegung von a/b vorkommen. Hier für das Beispiel mit hervorgehobenen Ziffern:

1071 = 1029 × 1 + 42
1029 = 42 × 24 + 21
42 = 21 × 2 + 0
Hieraus kann man ablesen dass
<math>\frac{1071}{1029} = \mathbf{1} + \frac{1}{\mathbf{24} + \frac{1}{\mathbf{2}}}</math>.

Dieses Verfahren lässt sich auch für beliebige reelle Zahl r anwenden. Ist r nicht rational so endet der Algorithmus nie. Die so gewonnene Folge an Quotienten dann die unendliche Kettenbruchzerlegung von r dar.

Erweiterung

Merkt man sich die Quotienten bei 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 hinter dem Quadratischen Reziprozitätsgesetz steckt. Damit lässt sich das Jacobi-Symbol effizient berechnen.

siehe auch: kgV und ggT Computerprogramm



Bücher zum Thema Euklidischer Algorithmus

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Euklidischer_Algorithmus.html">Euklidischer Algorithmus </a>