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)
- 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)
Kettenbruchentwicklung
Da der Artikel Kettenbruch noch nicht existiert, bitte ich an dieser Stelle um ein Beispiel: Wie sieht die "Kettenbruchentwicklung durch den Euklidischen Algorithmus", von dem im Artikel gesprochen wird, im Falle einer "beliebigen reelle Zahl r" aus? Ich kann mir darunter nix vorstellen. --SirJective 16:54, 20. Feb 2004 (CET)
- Vielleicht wirst Du hieraus schlau (ich knabbere noch): goldene Schnitt.pdf --Arbol01 23:59, 30. Apr 2004 (CEST)
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)