L'algoritmo di Euclide è un algoritmo matematico atto a calcolare il massimo comun divisore (ossia l'MCD) tra due numeri interi.
Rappresenta uno degli algoritmi più antichi oggi noti, figurando negli Elementi di EuclideF. Acerbi, Euclide, Tutte le opere, 2007, Bompiani. Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications datati al 300 a.C.; tuttavia, la sua effettiva scoperta potrebbe essere avvenuta circa due secoli prima. L'algoritmo, che non richiede la fattorizzazione dei due interi, era sicuramente noto a Eudosso di Cnido intorno al 375 a.C. e ad Aristotele che intorno al 330 a.C. ne fece cenno nell'opera I topici (158b, 29-35).
Il nome dell'algoritmo deriva dal matematico Euclide, da cui è tratta l'intuizione fondamentale.
Se e sono due numeri interi e è uno dei loro divisori comuni, per definizione possiamo dire che divide sia sia .
La divisione con resto in cui è il dividendo e è il divisore è descritta dalla formula da cui segue che . Sostituendo e per intero che divide e , si ottiene , da cui si deduce che divide . In generale, ogni divisore comune tra e è anche un divisore di . Viceversa, dato un divisore che divide sia sia , allora divide anche . Pertanto, il massimo comun divisore tra e è equivalente al massimo comun divisore tra e . Dato che il resto è sempre strettamente minore del divisore , lavorare su significa lavorare su numeri più piccoli.
Da un punto di vista pratico, l'algoritmo prevede che si controlli se è zero. Se lo è, è il MCD. Se non lo è, si deve dividere per e definire come il resto della divisione. Se allora si può affermare che è il MCD cercato; altrimenti occorre assegnare e e ripetere la divisione. L'algoritmo può essere quindi implementato sia per via ricorsiva sia per via iterativa.
Tenendo nota dei quozienti ottenuti durante lo svolgimento dell'algoritmo, si possono determinare due interi e tali che . 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 l'operazione di divisione con resto. Ad esempio, l'algoritmo funziona per i polinomi a un'indeterminata su un campo K, per i polinomi omogenei a due indeterminate su un campo, o per gli interi gaussiani. Un oggetto algebrico in cui è possibile eseguire la divisione con il 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 all'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:
inizia leggi (a, b) finché b > 0 fai: r <- mod(a, b) a <- b b <- r fine ciclo scrivi (a, "è il massimo comun divisore cercato") finisci.
Dimostrazione della correttezza dell'algoritmo Siano e interi positivi assegnati, e sia il loro MCD. Definiamo la successione di ricorrenza corrispondente ai passi dell'algoritmo di Euclide: , , , e è il resto della divisione di per , cioè . Per definizione di resto nella divisione, per ogni , quindi la successione dei è strettamente decrescente, e quindi esiste un tale che . Vogliamo dimostrare che . Infatti, per induzione si ha per ogni che . Inoltre, sempre per induzione, divide per ogni , quindi divide anche per ogni , quindi .
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 è 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 cifre. Allora il tempo di calcolo reale è quindi .
Questo tempo è comunque considerevolmente migliore rispetto all'algoritmo euclideo originale, in cui l'operazione di modulo è effettuata mediante ripetute sottrazioni in passi. Di conseguenza, questa versione dell'algoritmo richiede un tempo pari a per numeri con cifre, o per il numero .
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 : 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 e sono proprio i numeri che compaiono nella rappresentazione in frazione continua della frazione . Si prenda l'esempio di e usato prima. Questi sono i calcoli con i quozienti in evidenza:
Da questo elenco si può vedere che . Questo metodo può anche essere usato per valori di e reali; se è irrazionale allora l'algoritmo euclideo non ha termine, ma la sequenza di quozienti che si calcola costituisce sempre la rappresentazione (ora infinita) di in frazione continua.
Codici
C e C++ (algoritmo iterativo) /* Algoritmo iterativo */ int euclide(int a, int b) { int r; // resto della divisione while(b != 0) //ripete finché non riduce b a zero
r = a % b; // in r salva il resto della divisione tra a e b a = b; // scambia il ruolo di a e b b = r; // in b ora c'è r = a % b
return a; //... e quando b è (o è diventato) 0, il risultato è in a }
C e C++ (algoritmo ricorsivo) /* Algoritmo ricorsivo */ int euclide(int a, int b) { if(b == 0) return(a); else return euclide(b, a % b); // la funzione richiama sé stessa }
Scala (algoritmo ricorsivo) @tailrec def euclide(a: Int, b: Int): Int = if (b == 0) a else euclide(b, a % b)
MATLAB (algoritmo iterativo) function out = euclide(a, b) if(b == 0) out = a; elseif(b == 1) out = 1; else out = euclide(b, mod(a,b)); end
end
Python (algoritmo iterativo) def euclide(a, b): while b: a, b = b, a % b return a
Ruby (algoritmo iterativo) def euclide(a, b) while b != 0 do a, b = b, a % b end a end
Pascal (algoritmo iterativo) function euclide(a, b: integer): integer; var r: integer; begin if b = 0 then MCD := a else begin r := (a mod b); while not (r = 0) do begin a := b; b := r; r := (a mod b); end; MCD := b; end; end;
BASIC (vb.net, algoritmo iterativo) Function Euclide(ByVal a As Int16, ByVal b As Int16) As Int16 Dim r As Int16 = a Mod b
While (r <> 0) a = b b = r r = a Mod b Wend
Return b End Function
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) function euclide($a, $b) { while ($b) { list($a, $b) = array($b, $a % $b);
return $a; }
Java (algoritmo iterativo) private static int euclide(int a, int b) { int r; while (b != 0) { r = a % b; a = b; b = r;
return Math.abs(a); }
Rust (algoritmo iterativo) fn euclide(mut a: u64, mut b: u64) -> u64 { assert! (a != 0 && b != 0); while b != 0 { let r = a % b; a = b; b = r;
a }
Go (algoritmo iterativo) func euclide(a, b int) int { for b != 0 { a, b = b, a%b } return a }
Note
Bibliografia Donald Knuth., 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 Algoritmo esteso di Euclide Equazione diofantea lineare Ritmo di Euclide Identità di Bézout
Altri progetti
Collegamenti esterni
Euclid's Algorithm su cut-the-knot Binary Euclid's Algorithm (Java) su cut-the-knot Euclid's Game (Java) su cut-the-knot
Euclide Categoria:Euclide