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^[1] 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 ${\displaystyle a}$ e ${\displaystyle b}$, l'algoritmo prevede che si controlli se ${\displaystyle b}$ è zero. Se lo è, ${\displaystyle a}$ è il MCD. Se non lo è, si deve dividere ${\displaystyle {\frac {a}{b}}}$ e definire ${\displaystyle r}$ come il resto della divisione (operazione indicata con "a modulo b" più sotto). Se ${\displaystyle r=0}$ allora si può affermare che ${\displaystyle b}$ è il MCD cercato, altrimenti occorre assegnare ${\displaystyle a'=b}$ e ${\displaystyle 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 ${\displaystyle p}$ e ${\displaystyle q}$ tali che ${\displaystyle 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.

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

inizia
    leggi (a, b)
    mentre b > 0 fai:
        r <- mod(a, b)
        a <- b
        b <- r
    fine ciclo
    scrivi (a, "è il massimo comun divisore cercato")
finisci.

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

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 ${\displaystyle 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 ${\displaystyle n}$ cifre. Allora il tempo di calcolo reale è quindi ${\displaystyle O(n^{2})}$.

Questo tempo è comunque considerevolmente migliore rispetto all'algoritmo euclideo originale, in cui l'operazione di modulo è effettuata mediante ripetute sottrazioni in ${\displaystyle O(2^{n})}$ passi. Di conseguenza, questa versione dell'algoritmo richiede un tempo pari a ${\displaystyle O(n2^{n})}$ per numeri con ${\displaystyle n}$ cifre, o ${\displaystyle O(m\log m)}$ per il numero ${\displaystyle 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 ${\displaystyle O(n^{2})}$: infatti su molte macchine reali permette di diminuire le costanti nascoste nella notazione "O grande".

I quozienti che compaiono quando l'algoritmo euclideo viene applicato ai valori di input ${\displaystyle a}$ e ${\displaystyle b}$ sono proprio i numeri che compaiono nella rappresentazione in frazione continua della frazione ${\displaystyle {\frac {a}{b}}}$. Si prenda l'esempio di ${\displaystyle a=1071}$ e ${\displaystyle b=1029}$ usato prima. Questi sono i calcoli con i quozienti in evidenza:

${\displaystyle 1071=1029\times \mathbf {1} +42}$

${\displaystyle 1029=42\times \mathbf {24} +21}$

${\displaystyle 42=21\times \mathbf {2} +0}$

Da questo elenco si può vedere che

${\displaystyle {\frac {1071}{1029}}=\mathbf {1} +{\frac {1}{\mathbf {24} +{\frac {1}{\mathbf {2} }}}}}$.

Questo metodo può anche essere usato per valori di ${\displaystyle a}$ e ${\displaystyle b}$ reali; se ${\displaystyle {\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 ${\displaystyle {\frac {a}{b}}}$ in frazione continua.

Questa voce o sezione sull'argomento informatica è ritenuta da controllare.

Motivo: Controllare se i codici vanno mantenuti o trasferiti ad un altro progetto

---

Partecipa alla discussione e/o correggi la voce. Segui i suggerimenti del progetto di riferimento.

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^[3] (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
}

• 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.

• Minimo comune multiplo
• Massimo comun divisore
• Algoritmo esteso di Euclide
• Equazione diofantea lineare
• Ritmo di Euclide
• Identità di Bézout

• Wikibooks contiene testi o manuali sull'algoritmo di Euclide
• Wikimedia Commons contiene immagini o altri file sull'algoritmo di Euclide

• euclidèo, algoritmo-, su sapere.it, De Agostini.
• Euclide, algoritmo di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Euclidean algorithm, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Opere riguardanti Euclidean algorithm, su Open Library, Internet Archive.
• (EN) Eric W. Weisstein, Euclidean Algorithm, su MathWorld, Wolfram Research.
• (EN) Euclidean algorithm, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) Denis Howe, Euclid's Algorithm, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
• (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

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

V · D · M Teoria dei numeri
Numeri più usati	Naturali · Interi · Pari e dispari
Principi generali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza
Successioni di interi	Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica
Congetture	Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet
Discipline connesse	Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica