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, si controlla se b è zero (questa prima fase rientra ovviamente nell'ambito di un uso moderno dell'algoritmo ed era ignorata da Euclide e dai suoi predecessori, che non conoscevano lo 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 per ogni n che 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 n cifre, 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 i 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 costituisce sempre la rappresentazione (ora infinita) di a/b in frazione continua.

Codici

C

int Euclide(int a, int b) // prototipo della funzione Euclide //
{
    int r;
    while(b != 0) //ripetere finché non riduciamo a zero
    {
         r = a % b;
         a = b; 
         b = r; //scambiamo il ruolo di a e b
    }
    return a; //... e quando b è (o è diventato) 0, il risultato è a
}

Linguaggio C

/*ALGORITMO RICORSIVO*/
int gcd(int m, int n)
  if(n==0)
     return(m);
  else
     return gcd(n,m%n);

Scala

@tailrec
def gcd(m: Int, n: Int): Int =
    if (n == 0)
      m
    else
      gcd(n, m % n)

MATLAB

function out= miogdc (a,b)
    if(b==0)
        out=a;
    
    elseif(b==1)
        out=1;
    else
        out=miogdc(b,mod(a,b));
    end
    
end

Python

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

Ruby

def euclide(a, b)
  while(b!=0) do
    a,b = b,a%b
  end
  return a
end

Pascal

function MCD(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)

    Function Euclide_MCD(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
        End While

        Return b

    End Function

In questo algoritmo è stato usato per la rappresentazione numerica il tipo "int16" ma può essere cambiata piacimento con qualsiasi altro tipo di variabile numerica secondo i bisogni del programma.

PHP

 function mcd($a,$b) {
	while($b) list($a,$b)=array($b,$a%$b);
	return $a;
}

Go

func mcd(a, b int) int {
    for b != 0 {
        a, b = b, a % b
    }

    return a
}

Note

^ (EN) Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications

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

(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] (EN) Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications

[1]