# Algoritmo di Euclide

L'algoritmo di Euclide è un algoritmo per trovare il massimo comune divisore (indicato di seguito con MCD) tra due numeri interi. È uno degli algoritmi più antichi conosciuti, essendo presente negli Elementi di Euclide intorno al 300 a.C.; tuttavia, probabilmente l'algoritmo non è stato scoperto da Euclide, ma potrebbe essere stato conosciuto anche 200 anni prima. Certamente era conosciuto da Eudosso di Cnido intorno al 375 a.C.; Aristotele (intorno al 330 a.C.) ne ha fatto cenno ne I topici, 158b, 29-35. L'algoritmo non richiede la fattorizzazione dei due interi.
Dati due numeri naturali $a$ e $b$, l'algoritmo prevede che si controlli se $b$ è zero. Se lo è, $a$ è il MCD. Se non lo è, si deve dividere ${\frac {a}{b}}$ e definire $r$ come il resto della divisione (operazione indicata con "a modulo b" più sotto). Se $r=0$ allora si può affermare che $b$ è il MCD cercato, altrimenti occorre assegnare $a'=b$ e $b'=r$ e ripetere nuovamente la divisione. L'algoritmo può essere espresso in modo naturale utilizzando la ricorsione in coda.
Tenendo nota dei quozienti ottenuti durante lo svolgimento dell'algoritmo, si possono determinare due interi $p$ e $q$ tali che $ap+bq=MCD(a,b)$. Questo è noto con il nome di algoritmo di Euclide esteso.
Questi algoritmi possono essere usati, oltre che con i numeri interi, in ogni contesto in cui è possibile eseguire la divisione col resto. Ad esempio, l'algoritmo funziona per i polinomi ad una indeterminata su un campo K, o polinomi omogenei a due indeterminate su un campo, o gli interi gaussiani. Un oggetto algebrico in cui è possibile eseguire la divisione col resto è chiamato anello euclideo.
Euclide originariamente formulò il problema geometricamente, per trovare una "misura" comune per la lunghezza di due segmenti, e il suo algoritmo procedeva sottraendo ripetutamente il più corto dal più lungo. Questo procedimento è equivalente alla implementazione seguente, che è molto meno efficiente del metodo indicato sopra.

## Pseudocodice

Una scrittura in pseudocodice dell'algoritmo (in cui «mod» indica il resto della divisione intera) è la seguente:

## Dimostrazione della correttezza dell'algoritmo

Siano $a$ e $b$ interi positivi assegnati, e sia $d$ il loro MCD. Definiamo la successione di ricorrenza corrispondente ai passi dell'algoritmo di Euclide: $a_{0}=a$, $b_{0}=b$, $a_{n+1}=b_{n}$, e $b_{n+1}$ è il resto della divisione di $a_{n}$ per $b_{n}$, cioè $a_{n}=q_{n}b_{n}+b_{n+1}$. Per definizione di resto nella divisione, $b_{n+1}<b_{n}$ per ogni $n$, quindi la successione dei $b_{n}$ è strettamente decrescente, e quindi esiste un $N$ tale che $b_{N}=0$. Vogliamo dimostrare che $d=a_{N}$. Infatti, per induzione si ha per ogni $n$ che $d|a_{n}=b_{n-1}=a_{n-2}-q_{n-2}b_{n-2}$. Inoltre, sempre per induzione, $a_{N}$ divide $a_{n}$ per ogni $n\leq N$, quindi divide anche $b_{n}$ per ogni $n<N$, quindi $a_{N}=d$.

## Tempo di calcolo

Quando si analizza il tempo di calcolo dell'algoritmo di Euclide, si trova che i valori di input che richiedono il maggior numero di divisioni sono due successivi numeri di Fibonacci, e il caso peggiore richiede O(n) divisioni, dove $n$ è il numero di cifre nell'input. Occorre anche notare che le divisioni non sono operazioni atomiche (se i numeri sono più grandi della dimensione naturale delle operazioni aritmetiche del computer), visto che la dimensione degli operandi può essere di $n$ cifre. Allora il tempo di calcolo reale è quindi $O(n^{2})$.
Questo tempo è comunque considerevolmente migliore rispetto all'algoritmo euclideo originale, in cui l'operazione di modulo è effettuata mediante ripetute sottrazioni in $O(2^{n})$ passi. Di conseguenza, questa versione dell'algoritmo richiede un tempo pari a $O(n2^{n})$ per numeri con $n$ cifre, o $O(m\log m)$ per il numero $m$.
L'algoritmo di Euclide è ampiamente usato nella pratica, specialmente per numeri piccoli, grazie alla sua semplicità. Un algoritmo alternativo, l'algoritmo del MCD binario, utilizza la rappresentazione binaria dei computer per evitare le divisioni e quindi aumentare l'efficienza, sebbene anch'esso sia dell'ordine di $O(n^{2})$: infatti su molte macchine reali permette di diminuire le costanti nascoste nella notazione "O grande".

## Frazioni continue

I quozienti che compaiono quando l'algoritmo euclideo viene applicato ai valori di input $a$ e $b$ sono proprio i numeri che compaiono nella rappresentazione in frazione continua della frazione ${\frac {a}{b}}$. Si prenda l'esempio di $a=1071$ e $b=1029$ usato prima. Questi sono i calcoli con i quozienti in evidenza:
    $1071=1029\times \mathbf {1} +42$
    $1029=42\times \mathbf {24} +21$
    $42=21\times \mathbf {2} +0$
Da questo elenco si può vedere che
    ${\frac {1071}{1029}}=\mathbf {1} +{\frac {1}{\mathbf {24} +{\frac {1}{\mathbf {2} }}}}$.
Questo metodo può anche essere usato per valori di $a$ e $b$ reali; se ${\frac {a}{b}}$ è irrazionale allora l'algoritmo euclideo non ha termine, ma la sequenza di quozienti che si calcola costituisce sempre la rappresentazione (ora infinita) di ${\frac {a}{b}}$ in frazione continua.

## Codici

C e C++ (algoritmo iterativo)
C e C++ (algoritmo ricorsivo)
Scala (algoritmo ricorsivo)
MATLAB (algoritmo iterativo)
Python (algoritmo iterativo)
Ruby (algoritmo iterativo)
Pascal (algoritmo iterativo)
BASIC (vb.net, algoritmo iterativo)
In questo algoritmo è stato usato per la rappresentazione numerica il tipo "int16", ma può essere cambiato a piacimento con qualsiasi altro tipo di variabile numerica secondo i bisogni del programma.
PHP (algoritmo iterativo)
Java (algoritmo iterativo)
Rust (algoritmo iterativo)
Go (algoritmo iterativo)