Míg az euklideszi algoritmus csak két egész szám, $a$ és $b$ legnagyobb közös osztóját (GCD) számítja ki, addig a kibővített változat megtalálja a módját annak, hogy a GCD-t $a$ és $b$ tekintetében is ábrázolja, azaz. $x$ és $y$ együtthatókat, amelyekre:

$$$a \cdot x + b \cdot y = \gcd(a, b)$$

Fontos megjegyezni, hogy mindig találunk ilyen ábrázolást, például $\gcd(55, 80) = 5$ tehát $5$-t a $55$ és $80$ kifejezések lineáris kombinációjaként tudjuk ábrázolni: A probléma általánosabb formáját a Lineáris diofantikus egyenletek című cikkben tárgyaljuk.Erre az algoritmusra fog épülni.

Algoritmus

Az $a$ és $b$ GCD-jét ebben a részben $g$-vel jelöljük.

Az eredeti algoritmus módosításai nagyon egyszerűek: Ha felidézzük az algoritmust, láthatjuk, hogy az algoritmus $b = 0$ és $a = g$ értékekkel végződik, és ezekre a paraméterekre könnyen találhatunk együtthatókat, mégpedig $g \cdot 1 + 0 \cdot 0 = g$.

Az együtthatókból kiindulva $(x, y) = (1, 0)$, visszafelé haladhatunk a rekurzív hívásokon.Már csak azt kell kitalálnunk, hogy a $(a, b)$-ről $(b, a \bmod b)$-ra való átmenet során hogyan változnak az $x$ és $y$ együtthatók.

Tegyük fel, hogy megtaláltuk a $(x_1, y_1)$ együtthatókat $(b, a \bmod b)$ esetén:

$$b \cdot x_1 + (a \bmod b) \cdot y_1 = g$$

és meg akarjuk találni a $(x, y)$ párt $(a, b)$ esetén:

$$ a \cdot x + b \cdot y = g$$

A $a \bmod b$-t a következőképpen ábrázolhatjuk:

$$ a \bmod b = a – \left\lfloor \frac{a}{b} \right\rfloor \cdot b$$

Ezt a kifejezést behelyettesítve a $(x_1, y_1)$ együttható egyenletébe megkapjuk:

$$ 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$$

és a tagok átrendezése után:

$$g = a \cdot y_1 + b \cdot \left( x_1 – y_1 \cdot \left\lfloor \frac{a}{b} \right\rfloor \right)$$

Megtaláltuk $x$ és $y$ értékét:

$$$\begin{cases}x = y_1 \\\\y = x_1 – y_1 \cdot \left\lfloor \frac{a}{b} \right\rfloor\end{cases} $$$

Implementáció

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;}

A fenti rekurzív függvény visszaadja a GCD-t és az együtthatók értékét x és y (amelyeket hivatkozással adunk át a függvénynek).

A kiterjesztett euklideszi algoritmus ezen implementációja negatív egész számokra is helyes eredményeket ad.

Iteratív változat

A kiterjesztett euklideszi algoritmust iteratív módon is meg lehet írni.mivel így elkerüljük a rekurziót, a kód egy kicsit gyorsabban fog futni, mint a rekurzív változatban.

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;}

Ha jobban megnézzük a a1 és b1 változót, észrevehetjük, hogy pontosan ugyanazokat az értékeket veszik fel, mint a normál euklideszi algoritmus iteratív változatában. Tehát az algoritmus legalább a helyes GCD-t kiszámítja.

Azért, hogy az algoritmus miért számítja ki a helyes együtthatókat is, ellenőrizhetjük, hogy a következő invariánsok bármikor (a while ciklus előtt és minden iteráció végén) érvényesek: $x \cdot a + y \cdot b = a_1$ és $x_1 \cdot a + y_1 \cdot b = b_1$.Triviális látni, hogy ez a két egyenlet az elején teljesül, és ellenőrizhetjük, hogy a ciklus iterációjában a frissítés továbbra is fenntartja ezeket az egyenlőségeket.

A végén tudjuk, hogy $a_1$ tartalmazza a GCD-t, tehát $x \cdot a + y \cdot b = g$.Ami azt jelenti, hogy megtaláltuk a szükséges együtthatókat.

A kódot még tovább optimalizálhatjuk, és a $a_1$ és $b_1$ változókat eltávolíthatjuk a kódból, és csak az $a$ és $b$ értékeket használhatjuk újra.Ha azonban így teszünk, elveszítjük a lehetőséget, hogy az invarianciákról vitatkozzunk.

GYakorlati feladatok

• 10104 – Euklideszi feladat
• GYM – (J) Egyszer volt, hol nem volt
• UVA – 12775 – Ajándékdilemma