Terwijl het Euclidean algoritme enkel de grootste gemene deler (GCD) van twee gehele getallen $a$ en $b$ berekent, vindt de extended versie ook een manier om GCD voor te stellen in termen van $a$ en $b$, d.w.z. coëfficiënten $x$ en $y$ waarvoor:

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

Het is belangrijk op te merken, dat we altijd zo’n voorstelling kunnen vinden, bijvoorbeeld $\gcd(55, 80) = 5$ daarom kunnen we $5$ voorstellen als een lineaire combinatie met de termen $55$ en $80$: $55 \cdot 3 + 80 \cdot (-2) = 5$

Een meer algemene vorm van dat probleem wordt besproken in het artikel over Lineaire Diophantiene Vergelijkingen.Het zal voortbouwen op dit algoritme.

Algoritme

We zullen de GCD van $a$ en $b$ in deze paragraaf aanduiden met $g$.

De wijzigingen in het oorspronkelijke algoritme zijn heel eenvoudig.Als we het algoritme in herinnering roepen, zien we dat het algoritme eindigt met $b = 0$ en $a = g$.Voor deze parameters kunnen we gemakkelijk coëfficiënten vinden, namelijk $g \cdot 1 + 0 \cdot 0 = g$.

Uitgaande van deze coëfficiënten $(x, y) = (1, 0)$, kunnen we achterwaarts gaan in de recursieve oproepen.We hoeven alleen maar uit te zoeken hoe de coëfficiënten $x$ en $y$ veranderen bij de overgang van $(a, b)$ naar $(b, a \bmod b)$.

Laten we aannemen dat we de coëfficiënten $(x_1, y_1)$ hebben gevonden voor $(b, a \bmod b)$:

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

en we willen het paar $(x, y)$ vinden voor $(a, b)$:

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

We kunnen $a \bmod b$ voorstellen als:

$$ a \bmod b = a – \lftsvloer \frac{a}{b}

Substitueren van deze uitdrukking in de coëfficiëntenvergelijking van $(x_1, y_1)$ geeft:

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

en na herschikking van de termen:

$g = a \dot y_1 + b \dot links( x_1 – y_1 \dot links \lfloor \frac{a}{b} \rechts)$$

We vinden de waarden van $x$ en $y$:

$$$begin{gevallen}x = y_1 \y = x_1 – y_1 \cdot \leftlfloor \frac{a}{b}

Implementatie

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

De bovenstaande recursieve functie geeft de GCD en de waarden van de coëfficiënten aan x en y (die als referentie aan de functie worden doorgegeven).

Deze implementatie van het uitgebreide Euclidische algoritme geeft ook voor negatieve gehele getallen de juiste resultaten.

Iteratieve versie

Het is ook mogelijk om het uitgebreide Euclidische algoritme op een iteratieve manier te schrijven.Omdat het recursie vermijdt, zal de code iets sneller lopen dan de recursieve.

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

Als je goed kijkt naar de variabelen a1 en b1, zie je dat ze precies dezelfde waarden aannemen als in de iteratieve versie van het normale Euclidische algoritme. Het algoritme berekent dus in ieder geval de juiste GCD.

Om te zien waarom het algoritme ook de juiste coëfficiënten berekent, kun je nagaan dat de volgende invarianten op elk moment (voor de while-lus, en aan het eind van elke iteratie) zullen gelden: $x \cdot a + y \cdot b = a_1$ en $x_1 \cdot a + y_1 \cdot b = b_1$.Het is triviaal om te zien dat aan deze twee vergelijkingen in het begin voldaan is. En je kan controleren dat de update in de lus iteratie deze vergelijkingen nog steeds geldig houdt.

Op het einde weten we dat $a_1$ de GCD bevat, dus $x \cdot a + y \cdot b = g$.Wat betekent dat we de vereiste coëfficiënten hebben gevonden.

Je kan de code zelfs nog meer optimaliseren, en de variabelen $a_1$ en $b_1$ uit de code verwijderen, en enkel $a$ en $b$ hergebruiken.Maar als je dat doet, verlies je de mogelijkheid om te argumenteren over de invarianten.

Praktijkopgaven

• 10104 – Euclidesprobleem
• GYM – (J) Once Upon A Time
• UVA – 12775 – Geschenkendilemma