Berechnung ggT(x,y)

Neue Frage »

Romaxx Auf diesen Beitrag antworten »
Berechnung ggT(x,y)
Hallo zusammen,

der für natürliche Zahlen kann mit Hilfe des eukl. Algorithmus berechnet werden

Auf der deutschen Wiki-Seite hierzu findet man für die Laufzeit das folgende Bild:

[attach]56830[/attach]

Warum ist dieses Bild nicht symmetrisch um die Diagonale?

Danke.
HAL 9000 Auf diesen Beitrag antworten »

Hast du die Legende dieses Bildes gelesen? Dargestellt ist NICHT der ggT-Wert, sondern die Anzahl der Algorithmenschleifen, bis der ggT fest steht. Und für (x,y) mit x<y ist das genau ein Schleife mehr als für (y,x):

Und zwar ist das die erste Zeile .
Romaxx Auf diesen Beitrag antworten »

Danke.

Mir war schon klar, dass nicht der ggT dargestellt wird, sondern die Laufzeit.

Wenn also der Algo wüsste, welche Zahl die Größere ist, wäre das Bild symmetrisch.
HAL 9000 Auf diesen Beitrag antworten »

Ja. Aber der dargestellte Algorithmus macht eben nicht eine solche Vorab-Überprüfung.

M.E. ist das Bild mit Graustufen aussagekräftiger:

[attach]56832[/attach]

Je heller, desto mehr Schritte benötigt der Algorithmus. Am hellsten ist es dann entlang der Linie mit Steigung des Goldenen Schnittes, d.h. . Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »