Mentre l’algoritmo euclideo calcola solo il massimo comune divisore (GCD) di due interi $a$ e $b$, la versione estesa trova anche un modo per rappresentare GCD in termini di $a$ e $b$, cioè coefficienti $x$ e $y$ per i quali:

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

È importante notare che possiamo sempre trovare una tale rappresentazione, per esempio $\gcd(55, 80) = 5$ quindi possiamo rappresentare $5$ come una combinazione lineare con i termini $55$ e $80$: $55 \cdot 3 + 80 \cdot (-2) = 5$

Una forma più generale di questo problema è discussa nell’articolo sulle Equazioni Lineari Diofantine.Si baserà su questo algoritmo.

Algoritmo

In questa sezione denoteremo il GCD di $a$ e $b$ con $g$.

Le modifiche all’algoritmo originale sono molto semplici.Se ricordiamo l’algoritmo, possiamo vedere che l’algoritmo termina con $b = 0$ e $a = g$.Per questi parametri possiamo facilmente trovare i coefficienti, cioè $g \cdot 1 + 0 \cdot 0 = g$.

Partendo da questi coefficienti $(x, y) = (1, 0)$, possiamo risalire le chiamate ricorsive.Tutto quello che dobbiamo fare è capire come cambiano i coefficienti $x$ e $y$ durante il passaggio da $(a, b)$ a $(b, a \bmod b)$.

Immaginiamo di aver trovato i coefficienti $(x_1, y_1)$ per $(b, a \bmod b)$:

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

e vogliamo trovare la coppia $(x, y)$ per $(a, b)$:

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

Possiamo rappresentare $a \bmod b$ come:

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

Sostituendo questa espressione nell’equazione del coefficiente di $(x_1, y_1)$ si ottiene:

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

e dopo aver riorganizzato i termini:

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

Abbiamo trovato i valori di $x$ e $y$:

$$$begin{caso}x = y_1 \y = x_1 – y_1 \cdot \left\lfloor \frac{a}{b} \$$

Implementazione

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

La funzione ricorsiva di cui sopra restituisce il GCD e i valori dei coefficienti a x e y (che sono passati per riferimento alla funzione).

Questa implementazione dell’algoritmo euclideo esteso produce risultati corretti anche per gli interi negativi.

Versione iterativa

È anche possibile scrivere l’algoritmo euclideo esteso in modo iterativo.Poiché evita la ricorsione, il codice sarà un po’ più veloce di quello ricorsivo.

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

Se si guarda attentamente la variabile a1 e b1, si può notare che prendono esattamente gli stessi valori della versione iterativa del normale algoritmo euclideo. Quindi l’algoritmo calcolerà almeno il GCD corretto.

Per vedere perché l’algoritmo calcola anche i coefficienti corretti, potete verificare che i seguenti invarianti terranno in qualsiasi momento (prima del ciclo while, e alla fine di ogni iterazione): $x \cdot a + y \cdot b = a_1$ e $x_1 \cdot a + y_1 \cdot b = b_1$.È banale vedere che queste due equazioni sono soddisfatte all’inizio e si può verificare che l’aggiornamento nell’iterazione del ciclo manterrà ancora valide queste uguaglianze.

Alla fine sappiamo che $a_1$ contiene il GCD, quindi $x \cdot a + y \cdot b = g$.Il che significa che abbiamo trovato i coefficienti richiesti.

Si può anche ottimizzare ulteriormente il codice, e rimuovere la variabile $a_1$ e $b_1$ dal codice, e riutilizzare solo $a$ e $b$.Tuttavia, se lo fai, perdi la possibilità di discutere le invarianti.

Problemi pratici

• 10104 – Problema di Euclide
• GYM – (J) Once Upon A Time
• UVA – 12775 – Gift Dilemma