Mens den euklidiske algoritme kun beregner den største fælles divisor (GCD) af to hele tal $a$ og $b$, finder den udvidede version også en måde at repræsentere GCD i form af $a$ og $b$, dvs. koefficienter $x$ og $y$, for hvilke:

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

Det er vigtigt at bemærke, at vi altid kan finde en sådan repræsentation, for eksempel $\gcd(55, 80) = 5$ derfor kan vi repræsentere $5$ som en lineær kombination med termerne $55$ og $80$: $55 \cdot 3 + 80 \cdot (-2) = 5$

En mere generel form af dette problem behandles i artiklen om Lineære diophantinske ligninger.Den vil bygge på denne algoritme.

Algoritme

Vi vil i dette afsnit betegne GCD af $a$ og $b$ med $g$.

Fra den oprindelige algoritme er ændringerne meget enkle. hvis vi genkalder algoritmen, kan vi se, at algoritmen slutter med $b = 0$ og $a = g$. for disse parametre kan vi let finde koefficienter, nemlig $g \cdot 1 + 0 \cdot 0 = g$.

Med udgangspunkt i disse koefficienter $(x, y) = (1, 0)$ kan vi gå baglæns op ad de rekursive opkald.Vi skal blot finde ud af, hvordan koefficienterne $x$ og $y$ ændrer sig under overgangen fra $(a, b)$ til $(b, a \bmod b)$.

Lad os antage, at vi har fundet koefficienterne $(x_1, y_1)$ for $(b, a \bmod b)$:

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

og vi ønsker at finde parret $(x, y)$ for $(a, b)$:

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

Vi kan repræsentere $a \bmod b$ som:

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

Substituerer man dette udtryk i koefficientligningen for $(x_1, y_1)$, får man:

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

og efter omarrangeringen af udtrykkene:

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

Vi har fundet værdierne for $x$ og $y$:

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

Implementering

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 rekursive funktion ovenfor returnerer GCD og værdierne af koefficienterne til x og y (som overføres som reference til funktionen).

Denne implementering af den udvidede euklidiske algoritme giver også korrekte resultater for negative hele tal.

Iterativ version

Det er også muligt at skrive den udvidede euklidiske algoritme på en iterativ måde. fordi den undgår rekursion, vil koden køre lidt hurtigere end den rekursive.

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

Hvis man ser nærmere på variablerne a1 og b1, kan man bemærke, at de tager nøjagtig de samme værdier som i den iterative version af den normale euklidiske algoritme. Algoritmen vil altså i det mindste beregne den korrekte GCD.

For at se, hvorfor algoritmen også beregner de korrekte koefficienter, kan man kontrollere, at følgende invarianter til enhver tid (før while-loop’en og ved slutningen af hver iteration) vil være gældende: $x \cdot a + y \cdot b = a_1$ og $x_1 \cdot a + y_1 \cdot b = b_1$.Det er trivielt at se, at disse to ligninger er opfyldt i begyndelsen, og man kan kontrollere, at opdateringen i loop-iterationen stadig vil holde disse ligninger gyldige.

I slutningen ved vi, at $a_1$ indeholder GCD, så $x \cdot a + y \cdot b = g$. hvilket betyder, at vi har fundet de nødvendige koefficienter.

Du kan endda optimere koden mere, og fjerne variablen $a_1$ og $b_1$ fra koden, og blot genbruge $a$ og $b$.Men hvis du gør det, mister du muligheden for at argumentere for invarianterne.

Praksisopgaver

• 10104 – Euklid Problem
• GYM – (J) Once Upon A Time
• UVA – 12775 – Gave-dilemma