Euklidischer Algorithmus und Laufzeit

Der euklidische Algorithmus berechnet den grössten gemeinsamen Teiler ggT(a, b). Die modulo-Variante ersetzt das Paar (a, b) durch (b, a mod b), bis der Rest 0 ist. Dann ist der aktuelle Wert von b der ggT.

Beispiel: ggT(92, 32): 92 = 2*32 + 28, weiter mit (32, 28), (28, 4), (4, 0). Ergebnis 4.

Für aufeinanderfolgende Fibonacci-Zahlen ist die modulo-Variante deutlich sparsamer als wiederholtes Subtrahieren: die Schrittzahl wächst mit der Grösse der Zahlen nur langsam (logarithmisch). Die Subtraktionsvariante kann linear viele Schritte brauchen.

Der Algorithmus ist determiniert: gleiche Eingaben liefern denselben ggT.

$$\gcd(a,b)=\gcd(b,a \bmod b)$$

Wo gebraucht

Baustein in Kryptografie (modulare Inverse, RSA-Vorbereitung), Bruchkürzen, Takt-/Sample-Raten angleichen, Gitter- und Zahlentheorie-Code. Die logarithmische Schrittzahl ist der Grund, warum GCD auch bei grossen Integers alltagstauglich bleibt.

Vertiefung

Der Algorithmus beruht auf der Invariante ggT(a, b) = ggT(b, a mod b). Jeder Schritt ersetzt das Paar durch ein kleineres äquivalentes Problem. Sobald der zweite Wert null ist, enthält der erste den gesuchten Teiler.

Der Rest kann im ungünstigen Fall nur langsam schrumpfen. Die langsamsten Folgen stehen eng mit aufeinanderfolgenden Fibonacci-Zahlen in Verbindung. Trotzdem wächst die Schrittzahl nur proportional zur Stellenzahl der Eingabe und nicht proportional zu ihrem Zahlenwert.

Die iterative Form benötigt konstanten Zusatzspeicher. Die rekursive Form bildet dieselbe Zustandsfolge im Aufrufspeicher ab und ist mathematisch knapp, bringt in Java aber keinen automatischen Speichergewinn.

Schwierigkeitsstufen

1. Restschritte für zwei positive Zahlen ausführen.
2. Die ggT-Invariante mit der Division mit Rest begründen.
3. Den Fibonacci-Zusammenhang für ungünstige Eingaben erklären.

Fallstricke

Ein häufiger Fehler ist die Verwechslung von Quotient und Rest. Für negative Eingaben oder a = b = 0 muss ausserdem festgelegt werden, welche Vorbedingungen und Vorzeichenkonventionen gelten.