Während der euklidische Algorithmus nur den größten gemeinsamen Teiler (GCD) von zwei ganzen Zahlen $a$ und $b$ berechnet, findet die erweiterte Version auch einen Weg, GCD in Form von $a$ und $b$ darzustellen, d.h. Koeffizienten $x$ und $y$, für die gilt:
$$$a \cdot x + b \cdot y = \gcd(a, b)$$
Es ist wichtig anzumerken, dass wir immer eine solche Darstellung finden können, z.B. $\gcd(55, 80) = 5$ also können wir $5$ als Linearkombination mit den Termen $55$ und $80$ darstellen: $55 \cdot 3 + 80 \cdot (-2) = 5$
Eine allgemeinere Form dieses Problems wird in dem Artikel über Lineare Diophantische Gleichungen behandelt.Er baut auf diesem Algorithmus auf.
Algorithmus
Wir werden in diesem Abschnitt den GCD von $a$ und $b$ mit $g$ bezeichnen.
Die Änderungen am ursprünglichen Algorithmus sind sehr einfach.Wenn wir uns den Algorithmus ins Gedächtnis rufen, sehen wir, dass der Algorithmus mit $b = 0$ und $a = g$ endet.Für diese Parameter können wir leicht Koeffizienten finden, nämlich $g \cdot 1 + 0 \cdot 0 = g$.
Ausgehend von diesen Koeffizienten $(x, y) = (1, 0)$ können wir die rekursiven Aufrufe rückwärts gehen.Wir müssen nur noch herausfinden, wie sich die Koeffizienten $x$ und $y$ beim Übergang von $(a, b)$ zu $(b, a \bmod b)$ ändern.
Angenommen, wir haben die Koeffizienten $(x_1, y_1)$ für $(b, a \bmod b)$ gefunden:
$$b \cdot x_1 + (a \bmod b) \cdot y_1 = g$$
und wir wollen das Paar $(x, y)$ für $(a, b)$ finden:
$$ a \cdot x + b \cdot y = g$$
Wir können $a \bmod b$ darstellen als:
$$ a \bmod b = a – \left\lfloor \frac{a}{b} \right\rfloor \cdot b$$
Einsetzen dieses Ausdrucks in die Koeffizientengleichung von $(x_1, y_1)$ ergibt:
$$ g = b \cdot x_1 + (a \bmod b) \cdot y_1 = b \cdot x_1 + \left(a – \left\lfloor \frac{a}{b} \right\rfloor \cdot b \right) \cdot y_1$$
und nach Umordnung der Terme:
$$g = a \cdot y_1 + b \cdot \left( x_1 – y_1 \cdot \left\lfloor \frac{a}{b} \right\rfloor \right)$$
Wir fanden die Werte von $x$ und $y$:
$$$begin{cases}x = y_1 \\\y = x_1 – y_1 \cdot \left\lfloor \frac{a}{b} \right\rfloor\end{cases} $$
Implementierung
int gcd(int a, int b, int& x, int& y) { if (b == 0) { x = 1; y = 0; return a; } int x1, y1; int d = gcd(b, a % b, x1, y1); x = y1; y = x1 - y1 * (a / b); return d;}Die obige rekursive Funktion liefert den GCD und die Werte der Koeffizienten zu x und y (die per Referenz an die Funktion übergeben werden).
Diese Implementierung des erweiterten euklidischen Algorithmus liefert auch für negative ganze Zahlen korrekte Ergebnisse.
Iterative Version
Es ist auch möglich, den erweiterten euklidischen Algorithmus iterativ zu schreiben.
int gcd(int a, int b, int& x, int& y) { x = 1, y = 0; int x1 = 0, y1 = 1, a1 = a, b1 = b; while (b1) { int q = a1 / b1; tie(x, x1) = make_tuple(x1, x - q * x1); tie(y, y1) = make_tuple(y1, y - q * y1); tie(a1, b1) = make_tuple(b1, a1 - q * b1); } return a1;}Wenn man sich die Variablen a1 und b1 genau ansieht, kann man feststellen, dass sie genau die gleichen Werte annehmen wie in der iterativen Version des normalen euklidischen Algorithmus. Der Algorithmus berechnet also zumindest den korrekten GCD.
Um zu sehen, warum der Algorithmus auch die korrekten Koeffizienten berechnet, kann man überprüfen, dass die folgenden Invarianten zu jedem Zeitpunkt (vor der while-Schleife und am Ende jeder Iteration) gelten: $x \cdot a + y \cdot b = a_1$ und $x_1 \cdot a + y_1 \cdot b = b_1$.Es ist trivial zu sehen, dass diese beiden Gleichungen am Anfang erfüllt sind, und man kann überprüfen, dass die Aktualisierung in der Iterationsschleife diese Gleichheiten weiterhin gültig hält.
Am Ende wissen wir, dass $a_1$ den GCD enthält, also $x \cdot a + y \cdot b = g$.Das bedeutet, dass wir die benötigten Koeffizienten gefunden haben.
Man kann den Code sogar noch weiter optimieren und die Variablen $a_1$ und $b_1$ aus dem Code entfernen, und nur $a$ und $b$ wiederverwenden.Wenn du das tust, verlierst du jedoch die Möglichkeit, über die Invarianten zu argumentieren.
Praxisprobleme
- 10104 – Euklidisches Problem
- GYM – (J) Once Upon A Time
- UVA – 12775 – Geschenkdilemma