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 $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^[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.

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)

/* 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
}

Note

^ F. Acerbi, Euclide, Tutte le opere, 2007, Bompiani. (EN) Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications
^ Euclide, algoritmo di - Treccani, su Treccani. URL consultato il 27 dicembre 2023.
^ (EN) Programming Rust, su GitHub. URL consultato il 6 gennaio 2023.

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

Altri progetti

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

Collegamenti esterni

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

Controllo di autorità	GND (DE) 4659898-4

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

[1] F. Acerbi, Euclide, Tutte le opere, 2007, Bompiani. (EN) Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications

[2] Euclide, algoritmo di - Treccani, su Treccani. URL consultato il 27 dicembre 2023.

[3] (EN) Programming Rust, su GitHub. URL consultato il 6 gennaio 2023.

[1]

[2]

[3]

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