Algoritmo di Euclide

L'algoritmo di Euclide è un algoritmo per trovare il massimo comun 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, si controlla se b è zero. Se lo è, a è il MCD. Se non lo è, si divide a / b e si assegna ad r il resto della divisione (operazione indicata con "a modulo b" più sotto). Se r = 0 allora si può terminare affermando che b è il MCD cercato, altrimenti occorre assegnare a = b e b = r e si ripete nuovamente la divisione. L'algoritmo può essere anche 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:

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₀ = a, b₀ = b, a_n+1=b_n, e b_n+1 è il resto della divisione di a_n per b_n, cioè a_n = q_nb_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 che per ogni n, d|a_n = b_n-1 = a_n-2 - q_n-2b_n-2. Inoltre, sempre per induzione, a_N divide a_n per ogni n≤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²).

Questo tempo è comunque considerevolmente migliore rispetto all'algoritmo euclideo originale, in cui l'operazione di modulo è effettuata mediante ripetute sottrazioni in O(2ⁿ) passi. Di conseguenza, questa versione dell'algoritmo richiede un tempo pari a O(n2ⁿ) per numeri con ncifre, o O(mlog 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²): 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 a/b. Si prenda l'esempio di a = 1071 e b = 1029 usato prima. Questi sono i calcoli con in quozienti in evidenza:

1071 = 1029 × 1 + 42

1029 = 42 × 24 + 21

42 = 21 × 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 a/b è irrazionale allora l'algoritmo euclideo non ha termine, ma la sequenza di quozienti che si calcola rappresenta sempre la rappresentazione (ora infinita) di a/b in frazione continua.

Algoritmo di Euclide scritto in C basato sul processo iterativo

int Euclide(int a, int b)  // prototipo della funzione Euclide //
{
    int r;
    r = a % b;             // operazione modulo //
    while(r != 0)          // ciclo di iterazione //
    {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

Funzione che calcola l'MCD in Python utilizzando l'Algoritmo di Euclide

def MCD(a,b):
    while b != 0:
        a, b = b, a % b
    return a

Funzione che calcola l'MCD in Pascal utilizzando l'Algoritmo di Euclide

function MCD(a,b:integer):integer;
begin
 r:=(a mod b);
 while (r not=0)  do
  begin  
  a:=b;
  b:=r;
  r:=(a mod b);
 end;
 MCD:=b
end;

Bibliografia

• Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Sections 4.5.2–4.5.3, pp. 333–379.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, e Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.2: Greatest common divisor, pp. 856–862.

Voci correlate

• Minimo comune multiplo
• Massimo comun divisore

Altri progetti

• Commons

• Commons contiene file multimediali su Algoritmo di Euclide

Collegamenti esterni

• (EN) Euclid's Algorithm su cut-the-knot
• (EN) Binary Euclid's Algorithm (Java) su cut-the-knot
• (EN) Euclid's Game (Java) su cut-the-knot