Algoritmo di Euclide

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.

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)

@tailrecdef 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  aend

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 bEnd 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
• 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) Eric W. Weisstein, Algoritmo di Euclide, su MathWorld, Wolfram Research.
• (EN) Algoritmo di Euclide, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) Euclid's Algorithm, in Free On-line Dictionary of Computing, Denis Howe. 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

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