Algoritmo di Euclide

Da Wikipedia, l'enciclopedia libera.

L'algoritmo di Euclide è un algoritmo per trovare il massimo comun 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(ab). 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[modifica | modifica sorgente]

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: a0 = a, b0 = b, an+1=bn, e bn+1 è il resto della divisione di an per bn, cioè an = qnbn + bn+1. Per definizione di resto nella divisione, bn+1 < bn per ogni n, quindi la successione dei bn è strettamente decrescente, e quindi esiste un N tale che bN = 0. Vogliamo dimostrare che d = aN. Infatti, per induzione si ha che per ogni n, d|an = bn-1 = an-2 - qn-2bn-2. Inoltre, sempre per induzione, aN divide an per ogni nN, quindi divide anche bn per ogni n<N, quindi aN = d.

Tempo di calcolo[modifica | modifica sorgente]

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(2n) passi. Di conseguenza, questa versione dell'algoritmo richiede un tempo pari a O(n2n) 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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

C

int Euclide(int a, int b) // prototipo della funzione Euclide //
{
    if (b == 0) return a; // controlla che b non sia 0, in caso restituisce a //
 
    int r;
    r = a % b;             // operazione modulo //
    while(r != 0)          // ciclo di iterazione //
    {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

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;
begin
 if b=0 then 
  MCD:=a
 else begin
  r:=(a mod b);
  while (r not=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;
}

Note[modifica | modifica sorgente]

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

Bibliografia[modifica | modifica sorgente]

  • Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Sections 4.5.2–4.5.3, pp. 333–379.
  • Thomas H. Cormen, 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[modifica | modifica sorgente]

Altri progetti[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]