Algoritmo di Euclide

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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 e , l'algoritmo prevede che si controlli se è 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 il concetto di zero). Se lo è, è il MCD. Se non lo è, si deve dividere e definire come il resto della divisione (operazione indicata con "a modulo b" più sotto). Se allora si può affermare che è il MCD cercato, altrimenti occorre assegnare e 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 e tali che . 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 wikitesto]

Siano e interi positivi assegnati, e sia il loro MCD. Definiamo la successione di ricorrenza corrispondente ai passi dell'algoritmo di Euclide: , , , e è il resto della divisione di per , cioè . Per definizione di resto nella divisione, per ogni , quindi la successione dei è strettamente decrescente, e quindi esiste un tale che . Vogliamo dimostrare che . Infatti, per induzione si ha per ogni che . Inoltre, sempre per induzione, divide per ogni , quindi divide anche per ogni , quindi .

Tempo di calcolo[modifica | modifica wikitesto]

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 è 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 cifre. Allora il tempo di calcolo reale è quindi .

Questo tempo è comunque considerevolmente migliore rispetto all'algoritmo euclideo originale, in cui l'operazione di modulo è effettuata mediante ripetute sottrazioni in passi. Di conseguenza, questa versione dell'algoritmo richiede un tempo pari a per numeri con cifre, o per il numero .

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 : infatti su molte macchine reali permette di diminuire le costanti nascoste nella notazione "O grande".

Frazioni continue[modifica | modifica wikitesto]

I quozienti che compaiono quando l'algoritmo euclideo viene applicato ai valori di input e sono proprio i numeri che compaiono nella rappresentazione in frazione continua della frazione . Si prenda l'esempio di e usato prima. Questi sono i calcoli con i quozienti in evidenza:

Da questo elenco si può vedere che

.

Questo metodo può anche essere usato per valori di e reali; se è irrazionale allora l'algoritmo euclideo non ha termine, ma la sequenza di quozienti che si calcola costituisce sempre la rappresentazione (ora infinita) di in frazione continua.

Codici[modifica | modifica wikitesto]

C e 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
}

C e 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 cambiato a 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;
}

Java

  private static int MCD(int a, int b) {
        int a, int b, int r;
        while (b != 0) {
          r = a % b;
          a = b;
          b = r;
        }
        return Math.abs(a);
      }

Go

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

Note[modifica | modifica wikitesto]

  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

Bibliografia[modifica | modifica wikitesto]

  • 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[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Controllo di autoritàGND (DE4659898-4
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica