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'algoritmoModifica

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 per ogni n che d | an = bn-1 = an-2 - qn-2bn-2. Inoltre, sempre per induzione, aN divide an per ogni n ≤ N, quindi divide anche bn per ogni n < N, quindi aN = d.

Tempo di calcoloModifica

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 continueModifica

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

 .

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.

CodiciModifica

Questa voce o sezione sull'argomento informatica è ritenuta da controllare.
Motivo: Controllare se i codici vanno mantenuti o trasferiti ad un altro progetto
Partecipa alla discussione e/o correggi la voce. Segui i suggerimenti del progetto di riferimento.

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

NoteModifica

  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

BibliografiaModifica

  • 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 correlateModifica

Altri progettiModifica

Collegamenti esterniModifica

Controllo di autoritàGND (DE) 4659898-4
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica
Estratto da "https://it.wikipedia.org/w/index.php?title=Algoritmo_di_Euclide&oldid=117440530"