Medan den euklidiska algoritmen endast beräknar den största gemensamma divisorn (GCD) av två heltal $a$ och $b$, hittar den utökade versionen också ett sätt att representera GCD i termer av $a$ och $b$, dvs. koefficienter $x$ och $y$ för vilka:

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

Det är viktigt att notera att vi alltid kan hitta en sådan representation, t.ex. $\gcd(55, 80) = 5$ därför kan vi representera $5$ som en linjärkombination med termerna $55$ och $80$: $55 \cdot 3 + 80 \cdot (-2) = 5$

En mer allmän form av detta problem diskuteras i artikeln om Linjära diophantinska ekvationer.Den kommer att bygga på denna algoritm.

Algoritm

Vi kommer att beteckna GCD av $a$ och $b$ med $g$ i detta avsnitt.

Förändringarna i förhållande till den ursprungliga algoritmen är mycket enkla. om vi återkallar algoritmen kan vi se att algoritmen slutar med $b = 0$ och $a = g$. för dessa parametrar kan vi enkelt hitta koefficienter, nämligen $g \cdot 1 + 0 \cdot 0 = g$.

Med utgångspunkt i dessa koefficienter $(x, y) = (1, 0)$ kan vi gå bakåt uppåt i de rekursiva anropen.Allt vi behöver göra är att ta reda på hur koefficienterna $x$ och $y$ förändras under övergången från $(a, b)$ till $(b, a \bmod b)$.

Låt oss anta att vi har hittat koefficienterna $(x_1, y_1)$ för $(b, a \bmod b)$:

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

och vi vill hitta paret $(x, y)$ för $(a, b)$:

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

Vi kan representera $a \bmod b$ som:

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

Substituera detta uttryck i koefficientekvationen för $(x_1, y_1)$ ger:

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

och efter att ha omlagt termerna:

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

Vi har hittat värdena för $x$ och $y$:

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

Implementation

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

Den rekursiva funktionen ovan returnerar GCD och värdena för koefficienterna till x och y (som överförs som referens till funktionen).

Denna implementering av den utvidgade euklidiska algoritmen ger korrekta resultat även för negativa heltal.

Iterativ version

Det är också möjligt att skriva den utvidgade euklidiska algoritmen på ett iterativt sätt. eftersom man då undviker rekursion kommer koden att köras lite snabbare än den rekursiva.

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

Om man tittar noga på variablerna a1 och b1 kan man märka att de tar exakt samma värden som i den iterativa versionen av den normala euklidiska algoritmen. Så algoritmen kommer åtminstone att beräkna den korrekta GCD.

För att se varför algoritmen också beräknar de korrekta koefficienterna kan du kontrollera att följande invarianter kommer att gälla vid varje tidpunkt (före while-slingan och i slutet av varje iteration): $x \cdot a + y \cdot b = a_1$ och $x_1 \cdot a + y_1 \cdot b = b_1$.Det är trivialt att se att dessa två ekvationer är uppfyllda i början, och du kan kontrollera att uppdateringen i loop-iterationen fortfarande kommer att hålla dessa likheter giltiga.

I slutet vet vi att $a_1$ innehåller GCD, så $x \cdot a + y \cdot b = g$.Vilket innebär att vi har hittat de nödvändiga koefficienterna.

Du kan till och med optimera koden mer och ta bort variablerna $a_1$ och $b_1$ från koden, och bara återanvända $a$ och $b$.Men om du gör det förlorar du möjligheten att argumentera om invarianterna.

Praktikproblem

• 10104 – Euklidproblemet
• GYM – (J) Once Upon A Time
• UVA – 12775 – Gåvodilemma