Diskussion:Euklidischer Algorithmus

Ursprüngliches Verfahren: Subtraktion vs. Division

Ist die binaere Version wirklich nuetzlich? Division mag zwar langsam sein, ist aber doch immer noch exponentiell schneller als widerholte Subtraktion. AxelBoldt 01:05, 24. Feb 2003 (CET)

Bitte schau dir den Algorithmus mal *genau* an. Es ist nicht nur eine wiederholte Subtraktion, sondern eine Kombination aus wiederholter Subtraktion und Division durch 2. Dadurch wird die Bitlänge der größeren der beiden "Restzahlen" kontinuierlich dekrementiert. Die Zahl der Bitoperationen ist im Worst Case O(k²), wobei k die Bitlänger ist. 80.128.234.194 23:28, 11. Sep 2003 (CEST)

---

IMHO ist die sprachliche Schilderung des klassischen Algorithmusses falsch. r wird nicht durch Subtraktion von m und n berechnet, sondern ist der Rest, der sich bei der Division von m durch n ergibt. Im Beispiel ist r zufällig auch die Differenz, weil 1071 durch 1029 ergibt: 1 Rest 42. Schon im zweiten Schritt zeigt sich aber, dass 1029 jetzt durch 42 geteilt wird, was 24 Rest 21 ergibt. --Andrsvoss 17:32, 4. Feb 2004 (CET)

Gegen Ende des Artikels ist die Rede von einem "faktoriellen Ring". Dieser Begriff sollte m. E. im Text erklärt werde. --Hanfried.lenz 18:05, 21. Okt. 2007 (CEST).

Das dachte ich beim Durchlesen auch, wollte aber nichts dran ändern, weil ich nicht sicher sagen kann, dass Euklid schon "geteilt" hat. Ich bin aber gerade dabei hier in der Bib über Euklid zu recherchieren. Leider haben wir den entsprechenden Band von Euklids Elementen nicht da. Zumindest habe ich ihn nicht gefunden.--Berni 17:59, 4. Feb 2004 (CET)

Ich habe gerade eine Übersetzung der Elemente gefunden und nachgesehen. Euklid beschreibt das Verfahren tatsächlich als Subtraktionsprozess, wie er beim klassischen Algorithmus geschildert wird. Ich arbeite das mal eben in den Artikel ein.--Berni 16:11, 10. Feb 2004 (CET)

Laufzeit

Zitat aus dem Artikel:

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 Laufzeit beträgt Θ(n), tatsächlich aber O(n²) klingt ziemlich blöd find ich. Auf welchen Algorithmus wollen wir uns hier eigentlich beziehen? Das Original von Euklid hat keine Division. Und wenn man schon große Zahlen beachtet, sollte man auch mal überlegen, was da jetzt die Subtraktionen kosten. Hat jemand da 'ne Idee, wie wir das alles unter einen Hut bekommen? --Berni 19:43, 9. Jul 2004 (CEST)

rekursiver Algorithmus der mit Subtraktion arbeitet

Weil es zum Teil recht wichtig ist, habe ich beim klassischen Algorithmus noch die rekursive Variante hinzugefügt, welche mit ggt(a,b) = ggt(a-b,b) oder ggt(a,b-a) arbeitet. Den Algorithmus zu kennen ist doch recht wichtig. Evt. kann das ja einer mit der richtigen Notation dazuschreiben (geschweifte klammern und so). Ich kann das leider nicht

Noch eine Frage zur Laufzeit

Die Laufzeit beträgt im schlimmsten Fall Θ(n), wobei n die Anzahl der Ziffern in der Eingabe ist (siehe Landau-Symbole).

Das bezieht sich wohl auf den Subtraktionsalgorithmus unter der Voraussetzung, dass eine Subtraktion in konstanter Zeit durchgeführt werden kann. Ich halte die Aussage für falsch, denn wählt man z. B. a = 1000 und b = 1, so wird 1000 Mal subtrahiert, und nicht etwa 4 Mal (die Anzahl der Ziffern in der Zahl 1000). Richtig wäre also: ..., wobei n = max{a, b} bzw. ..., wobei n = a + b. Kann das jemand bestätigen? --Head 00:04, 7. Jan 2006 (CET)

Mit "schlimmster Fall" sind Eingaben wie zwei aufeinanderfolgende Fibonacci-Zahlen $f_{n},f_{n+1}$ gemeint, bei denen auch der Divisionsalgorithmus nicht schneller als der Subtraktionsalgorithmus ist, beide brauchen $n$ Schritte. Da die Fibonacci-Zahlen exponentiell wachsen, passt das genau zu obiger Abschätzung.--Gunther 00:09, 7. Jan 2006 (CET)

Aber die aufeinanderfolgenden Fibonacci-Zahlen sind doch nur für den Divisionsalgorithmus der Worst Case, nicht für den Subtraktionsalgorithmus. --Head 00:22, 7. Jan 2006 (CET)

Da im darauffolgenden Satz die Rede von Division ist, würde ich sie auf den Divisionsalgorithmus beziehen. Der Subtraktionsalgorithmus hat natürlich $N,1$ als worst case mit Laufzeit $N=2^{n}$.--Gunther 00:27, 7. Jan 2006 (CET)

Beispiel

Der Algorithmus ist am einfachsten an einem Zahlenbeispiel erklärt:

Gesucht sei der ggT von 35 und 15.

$35=2\cdot 15+5$

In Worten: 35 geteilt durch 15 ergibt 2 und einen Rest 5.

Wenn sich, wie in diesem Fall ein Rest ungleich 0 ergibt, kann der ggT aus dem Rest, hier 5, und dem Divisor, hier 15, bestimmt werden. Wir ersetzten also die 35 durch den Rest 5 und wiederholen die Division mit Rest.

$15=3\cdot 5+0$

In Worten: 15 geteilt durch 5 ergibt 3 ohne Rest.

Falls sich wie in diesem Fall kein Rest ergibt, ist der ggT gleich dem Divisor. In unserem Beispiel 5.

Falls sich der Rest 1 ergibt, ist der ggT gleich 1. Da sich die Zahlen in jedem Schritt mindestens halbieren, ist das Verfahren auch bei großen Zahlen extrem schnell.

Ich finde, dass dieses Beispiel ueberhaupt nichts erklaert und auch nicht illustrativ ist. --DaTroll 12:52, 27. Mär 2006 (CEST)

Ich stimme zu. Das Beispiel sollte anschaulicher gestaltet werden.

--Roeme 09:15, 10. Mai 2006 (CEST)

Ich erwarte außerdem von einer Erklärung, dass sie auch erklärt, warum der Algorithmus richtig ist, und nicht nur, wie man ihn ausführt.

Gliederung/Rekursion

Irgendwie ist der Aufbau inzwischen ziemlich chaotisch. Die Trennung zwischen "Algorithmus" und "klassischem Algorithmus" ist unscharf (eigentlich sollte man wohl "Divisions-" und "Subtraktionsalgorithmus" trennen), und wieso die rekursive Form irgendwie besser sein soll, ist mir nicht klar (aber ich bin kein Informatiker, ich würd's nur so nicht implementieren).--Gunther 13:04, 29. Jun 2006 (CEST)

Ich habe mal mit der Überarbeitung begonnen. Der Vorteil (für Informatiker?) rekursiver Algorithmen liegt darin, dass sie meist einfacher zu verstehen und zu implementieren sind. Über die Qualität der Implementierung sagt das nichts aus ;-) --Squizzz 13:59, 29. Jun 2006 (CEST)

Hmnaja,

while b ≠ 0
   a, b ← b, a mod b
return a

ist hinsichtlich Einfachheit kaum zu überbieten.--Gunther 14:04, 29. Jun 2006 (CEST)

Einfacher ist obiger Divisions-Algorithmus wohl. Allerdings ist für mich die rekursive Variante trotzdem leichter verständlich. Auch in Introductions to Algorithms wird sie verwendet. Ich denke, dass man an ihr nach der Erklärung in Funktionsweise auch leichter sieht, wie die Eigenschaften des ggT ausgenutzt werden. --Squizzz 14:15, 29. Jun 2006 (CEST)

Wenn Du eine Referenz für die iterative Fassung suchst: TAOCP.--Gunther 14:17, 29. Jun 2006 (CEST)

Es sind jetzt sowohl eine iterative als auch eine rekursive Variante im Artikel. Der Leser kann sich dann aussuchen was ihm gefällt. Auch habe ich anstatt Divisions-Algorithmus die Bezeichnung moderner euklidischer Algorithmus wie in TAOCP gewählt. Dann kommt man nicht mit division algorithm (Division mit Rest) durcheinander. --Squizzz 00:25, 30. Jun 2006 (CEST)

Ist vielleicht ein wenig esoterisch, aber in logischen Programmiersprachen gehts nur rekursiv, z.B. in Prolog:

 gcd(A, 0, A).
 gcd(A, B, GCD) :- B>0, K is A mod B, gcd(B, K, GCD).

Aber auch wenn das in einer imperativen Programmiersprache so geschrieben wird, macht jeder vernünftige Compiler aus der tail recursion eine Iteration. --Horrorist 16:06, 1. Jul 2006 (CEST)

Beschreibung durch Pseudocode

Das "solange" sollte in der nichtrekursiven Variante ganz am Anfang stehen, nicht erst nach dem zweiten Vergleich, also "solange a ungleich null und b ungleich null", sonst bricht der Algorithmus nicht ab, wenn a später null wird und nicht gleich am Anfang null ist. --Hermann Steier (nicht signierter Beitrag von 178.191.162.183 (Diskussion) 21:59, 5. Dez. 2010 (CET))

Zitat aus dem Artikel:

Beide Algorithmen setzen voraus, dass $a\geq b$ ist. Will man diese Voraussetzung vermeiden, so muss jeweils eine Anweisung eingefügt werden, die im Fall $a<b$ die beiden Werte vertauscht.

Das ist meiner Meinung nach falsch. Im Fall a < b werden die Werte im ersten Schritt des Algorithmus automatisch vertauscht. --Gorx 19:02, 6. Jul 2006 (CEST)

Richtig. Hab's geändert. --Squizzz 19:40, 6. Jul 2006 (CEST)

Variablennamen

Es wäre schön, wenn in den textuellen Beschreibungen des Verfahrens die gleichen Variablennamen verwendet würden wie in den Code-Beispielen. (Nicht hier m,n oder q,r dort a,b,h). Programmieranfänger stolpern darüber. --Rat 03:27, 7. Jul 2006 (CEST)

Polynome mit Koeffizienten aus einem faktoriellen Ring

Bezeichnet man die dort vorgestellt Methode wirklich noch als euklidischen Algorithmus? Wenn nein, ist sie nicht sinnvoller bei ggT oder faktorieller Ring aufgehoben? --Squizzz 17:56, 7. Jul 2006 (CEST)

Sie ist zumindest aus dem euklidischen Algorithmus hervorgegangen. Collins nennt sie "Euklidische Polnomrestfolge", also nicht direkt Euklidischer Algorithmus. Brown und Traub wird der Euklidische Algorithmus genannt und dann direkt das Verfahren für Polynome mit Koeffizienten aus einem fakt. Ring eingeführt, ein extra Name steht da glaube ich nicht (muss nochmal nachgucken). Knuth beschreibt das Verfahren glaube ich auch, hab ihn aber gerade nicht zur Hand.

Eigentlich hatte ich vor, einen Artikel zu Polynomrestfolgen zu schreiben, die sind zur ggT-Berechnung in Polynomringen absoluter Standard, und bei Resultante wird auch das Subresultantenverfahren erwähnt, das ein Spezialfall davon ist. Dann könnte im Eukl. Alg.-Artikel einfach darauf verwiesen werden. Bin aber neu bei Wikipedia, und da soll man ja erstmal bestehende Artikel verändern... --FarSide 17:19, 10. Jul 2006 (CEST)

Dann lassen wir den jetzigen Abschnitt einfach stehen und wenn du deinen Artikel fertig hast ersetzen wir ihn durch eine kurze Anmerkung. --Squizzz 02:24, 12. Jul 2006 (CEST)

Hab jetzt den Knuth da: Der Algorithmus heißt dort Generalized Euclidean Algorithm, steht in Band II, 4.6.1, Algorithmus E. Aber der Polynomrestfolgen-Artikel ist in Arbeit... FarSide 04:04, 14. Jul 2006 (CEST)

Gelöschte Aussage

Soweit ich sehen kann, ist es im Ring $\mathbb {Z} [\mathrm {i} ]$ nicht möglich, den ggT von 3 und 6i mit dem "klassischen" e.A. berechnen.--Gunther 16:49, 4. Sep 2006 (CEST)

Mein Fehler. Sorry. --Squizzz 17:11, 4. Sep 2006 (CEST)

Der klassische Algorithmus

Der klassiche (nicht rekursive) Algorithmus terminiert nicht für b=1 und a=0. (nicht signierter Beitrag von 131.246.167.20 (Diskussion) 17:02, 6. Sep 2006)

Ganz klassisch wäre 0 sowieso keine gültige Eingabe, und die Abbruchbedingung lautet, dass eine der Zahlen die andere teilt: [1] --Gunther 17:18, 6. Sep 2006 (CEST)

Damit bin ich nicht ganz einverstanden. 0 wird von allen Zahlen geteilt. Der ggt von 0 und 1 ist demnach 0. Zumindest sollte es dann aber als Vorbedingung für den Algorithmus stehen, daß die 0 als Eingabe nicht erlaubt ist. (nicht signierter Beitrag von 131.246.161.4 (Diskussion) 13:13, 14. Sep 2006)

Mit "ganz klassisch" meinte ich, dass Euklid die 0 sicherlich nicht als mögliche Eingabe in Betracht gezogen hat. Ich wollte hauptsächlich sagen: Wenn man den Algorithmus ohnehin ändert, dann sollte man sich auch überlegen, ob man nicht die Abbruchbedingung wie o.a. anpasst.--Gunther 13:18, 14. Sep 2006 (CEST)

Zitat: "0 wird von allen Zahlen geteilt. Der ggt von 0 und 1 ist demnach 0." Es heißt doch aber "größter gemeinsamer TEILER" und nicht etwa "zu Teilender". 0 teilt nichts außer der 0, ansonsten gäb es schnell Widersprüche durch die Transitivität der Teilbarkeitsrelation. Also ist 0 höchstens der ggt von 0 und 0.

nicht-trivial

Da er der Algorithmus nicht-trivial ist, könnte jemand eine Erlärung hinzufügen wieso er überhaupt funktioniert?

In dem Artikel kommt der Begriff "faktorieller Ring" vor. Der sollte m. E. im Text erklärt werden. --Hanfried.lenz 18:10, 21. Okt. 2007 (CEST).

Einheitlichkeit!!

Im rekursiven Pseudo-Code ist ein Fehler bzw. eine Ungenauigkeit: einmal steht dort EUCLID_OLD_RECURSIVE, einmal ohne "_". Der Programmname wird mit Unterstrichen angegeben, also muss das auch in den Aufrufen so passieren. (Der vorstehende, nicht signierte Beitrag stammt von 87.172.241.9 (Diskussion • Beiträge) 08:01, 4. Mai 2008)

Es handelt sich um einen Darstellungsfehler im Firefox (IE wurde von mir nicht geprüft). Markiert man den Funktionsnamen und kopiert ihn in einen Texteditor, dann sind die Unterstriche vorhanden. --Stefan Birkner 11:34, 4. Mai 2008 (CEST)

Pennälergequatsche

Der Euklidische Algorithmus ist eben nicht "das schnellste Verfahren zur Berechnung des größten gemeinsamen Teilers"! Er war es vor 2000 Jahren. Unter sehr beschränkten und speziellen Randbedingungen ist eine pragmatische Variante davon das "schnellste Verfahren", sonst nicht. Diese Bedingungen sind im einfachen Schüler- und Lehrermillieu meistens gegeben oder werden vorausgesetzt, so daß die Beurteilung als pennälerhaft sachlich begründet ist. Die wesentliche Bedingung ist dabei, daß für die zu untersuchende Datenstruktur eine besonders effiziente Division bzw Divisionsrestbildung (Modulo) verfügbar ist. Bei ganzen, natürlichen Zahlen auf Taschenrechnern oder bei Java-Übungsaufgaben und selbst beim schulischen Kopfrechnen ist das der Fall. Wenn man schriftlich teilen muß ist der Algorithmus völlig unbrauchbar.

Die klassische Formulierung mit Subtraktionen in den "Elementen" von Euklid ist der Vorgabe der antiken griechischen Philosophie geschuldet, die fordert(e), daß eine mathematischen Behauptung mit den Mitteln und Regeln der Geometrie darstellbar, erklärbar und beweisbar sein muß. In der Praxis werden sich die alten Mathematiker schon immer mit moduloartigen Divisionen beholfen haben, die waren ja nicht blöd. Dies ist definitiv kein "moderner Euklidischer Algorithmus", erst recht nicht wegen des Verweis auf moderne Computertechnik.

Wenn diese Voraussetzungen nicht erfüllt sind, zB weil kein Modulo mit etwa linearem oder besserem Aufwand verfügbar ist, können andere Algorithmen deutlich besser sein. Wenn sich die Datenstruktur zB als p-stellige Summe von Potenzen, im einfachsten Fall zur Basis 2, darstellen läßt und gleichzeitig die Operationen Subtraktion und Schieben (DIvision durch die Basis) linearen Aufwand haben, dann kann der ggT trotzdem mit O(p^2) gefunden werden. Siehe Steinscher Algorithmus (1967) oder dessen Vereinfachung nach Brent (ca 1975). Letztere vermeidet mathematische Spitzfindigkeiten und Redundanzen. Diese Algorithmen als "binären Euklid" oder als Variante davon zu bezeichnen ist so sachgerecht wie ein Motorrad ein geteiltes Auto zu nennen.--46.115.74.232 18:55, 8. Dez. 2013 (CET)

Fehler in MathML

Hallo, ich bekomme in mehreren Browsern bei "Polynome" folgenden Fehler angezeigt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „/mathoid/local/v1/“:): x^{2}-1=\left({\frac {1}{2}}x-{\frac {1}{2}}\right)\cdot (2x+2)+0

Kann das einer reparieren? --212.185.166.50 13:26, 18. Okt. 2016 (CEST)

Pseudocode

Was sollen die ganzen // im Pseudocode, wenn da kein Kommentar auftaucht ? --Claude J (Diskussion) 09:46, 1. Jul. 2020 (CEST)

Damit soll offenbar das Ende eines eingerückten Codeblocks noch einmal ausdrücklich markiert werden, also diejenige Stelle, wo in manchen Programmiersprachen end oder eine geschlossene Klammer } stehen würde. Das ist natürlich nicht unbedingt nötig, aber es schadet auch nicht. Mit Zeilenkommentaren //, wie man sie aus C++ und – ursprünglich – aus BCPL kennt, hat das Symbol hier nichts zu tun. --89.247.126.186 19:07, 30. Jul. 2021 (CEST)

Kleinstes gemeinsames Vielfaches erwähnen?

Mit dem euklidischen Algorithmus berechnet man den größten gemeinsamen Teiler, und mit dessen Hilfe kann man wiederum auch das kleinste gemeinsame Vielfache effizient berechnen. Lohnt sich eine kurze Erwähnung im Artikel? Den Link in die umgekehrte Richtung gibt es schon. --2001:16B8:1889:FD00:E44A:B825:5CEC:3550 21:55, 27. Jul. 2021 (CEST)

Animation

Die Animation ist ganz interessant, und geht so auch recht hübsch auf, aber mit dem Euklidischen Algorithmus, wie er beschrieben ist, krieg ich sie nur mit Mühe unter einen Hut.

Ich erklär mal: Zunächst wird der Modulo des grünen Gesamtbereiches (1071) durch Orange (462) gebildet. Das ist der grüne Rest (147) oberhalb des zweiten gelben Quadrates. Im zweiten Schritt müsste nun betrachtet werden, wie oft dieser grüne Rest (147) in ein oranges Quadrat passt, und welchen Rest man dabei erhält. Statt dessen wird ein aus dem Hut gezaubertes blaues Quadrat drei Mal in den grünen Rest eingepasst.

Im Pseudocode wird an dieser Stelle eine Variablenzuweisung gemacht (der grüne Rest repräsentiert das gelbe Quadrat, das blaue den grünen Rest); diese Verwandlung bleibt hier unsichtbar und unerklärt. Damit hilft die Animation mE wenig. Es funktioniert, aber nur, wenn man die Werte und Koordinaten des Rechtecks sorgfältig wählt? Oder weil es einen tieferen mathematischen Zusammenhang mit den Wurzeln des Restes gibt? Insgesamt wirkt es so eher wie ein Zaubertrick, dessen Hintergründe man nicht kennt.

Eine algorithmusähnlichere Darstellung fällt mir auf Anhieb aber auch nicht ein. Die Einpassung mit den Streifen wird ziemlich schmal mit derart großen Werten. Die Verwandlung der Felder wäre vergleichsweise aufwendig zu animieren. --Skuckem (Diskussion) 14:46, 8. Aug. 2023 (CEST)