Vaikka Eukleideen algoritmi laskee vain kahden kokonaisluvun $a$ ja $b$ suurimman yhteisen jakaja (GCD), laajennetussa versiossa löydetään myös tapa esittää GCD:n suurimmat yhteiset jakaja (GCD) $a$:n ja $b$:n suhteen, ts. kertoimet $x$ ja $y$, joille:

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

On tärkeää huomata, että löydämme aina tällaisen esityksen, esimerkiksi $\gcd(55, 80) = 5$ joten voimme esittää $5$ lineaarikombinaationa termeistä $55$ ja $80$: $55 \cdot 3 + 80 \cdot (-2) = 5$

Tämän ongelman yleisempää muotoa käsitellään artikkelissa Lineaariset diofanttiyhtälöt.Se perustuu tähän algoritmiin.

Algoritmi

Merkitään $a$:n ja $b$:n GCD:tä $g$:llä tässä kappaleessa.

Muutokset alkuperäiseen algoritmiin ovat hyvin yksinkertaisia: Jos palautamme algoritmin mieleen, huomaamme, että algoritmi päättyy arvoihin $b = 0$ ja $a = g$.Näille parametreille löydämme helposti kertoimet, nimittäin $g \cdot 1 + 0 \cdot 0 = g$.

Alkaen näistä kertoimista $(x, y) = (1, 0)$ voimme mennä rekursiiviset kutsut taaksepäin.Meidän tarvitsee vain selvittää, miten kertoimet $x$ ja $y$ muuttuvat siirryttäessä arvosta $(a, b)$ arvoon $(b, a \bmod b)$.

Asettakaamme, että olemme löytäneet kertoimet $(x_1, y_1)$ tapauksessa $(b, a \bmod b)$:

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

ja haluamme löytää parin $(x, y)$ tapauksessa $(a, b)$:

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

Voidaan esittää $a \bmod b$ seuraavasti:

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

Tämän lausekkeen korvaaminen $(x_1, y_1)$:n kerroinyhtälöllä antaa:

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

ja kun termit on järjestetty uudelleen:

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

Löysimme arvot $x$ ja $y$:

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

Toteutus

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

Yllä oleva rekursiivinen funktio palauttaa GCD:n ja kertoimien arvot x:lle ja y:lle (jotka välitetään funktiolle viitteenä).

Tämä laajennetun Eukleideen algoritmin toteutus tuottaa oikeat tulokset myös negatiivisille kokonaisluvuille.

Iteratiivinen versio

On myös mahdollista kirjoittaa laajennettu Eukleideen algoritmi iteratiivisesti.koska siinä vältetään rekursiota, koodi toimii hieman nopeammin kuin rekursiivisessa.

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

Jos katsot tarkkaan muuttujia a1 ja b1, huomaat, että ne ottavat täsmälleen samat arvot kuin normaalin Eukleideen algoritmin iteratiivisessa versiossa. Algoritmi laskee siis ainakin oikean GCD:n.

Kun näet, miksi algoritmi laskee myös oikeat kertoimet, voit tarkistaa, että seuraavat invariantit ovat voimassa milloin tahansa (ennen while-silmukkaa ja jokaisen iteraation lopussa): $x \cdot a + y \cdot b = a_1$ ja $x_1 \cdot a + y_1 \cdot b = b_1$.On triviaalia nähdä, että nämä kaksi yhtälöä täyttyvät alussa, ja voit tarkistaa, että silmukan iteraatiossa tapahtuva päivitys pitää nämä yhtälöt edelleen voimassa.

Lopussa tiedämme, että $a_1$ sisältää GCD:n, joten $x \cdot a + y \cdot b = g$.Mikä tarkoittaa, että olemme löytäneet tarvittavat kertoimet.

Voit jopa optimoida koodia vielä enemmän, ja poistaa muuttujat $a_1$ ja $b_1$ koodista, ja käyttää vain $a$ ja $b$ uudelleen.Jos teet näin, menetät kuitenkin kyvyn väitellä invarianteista.

Harjoitusongelmia

• 10104 – Eukleidi-ongelma
• GYM – (J) Olipa kerran
• UVA – 12775 – Lahjadilemma