Algoritmo di Euclide
algoritmo per trovare il massimo comune divisore tra due numeri interi Da Wikipedia, l'enciclopedia libera
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. 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.
Pseudocodice
Una scrittura in pseudocodice dell'algoritmo (in cui «mod» indica il resto della divisione intera) è la seguente[2]:
inizia leggi (a, b) finché b > 0 fai: r <- mod(a, b) a <- b b <- r fine ciclo scrivi (a, "è il massimo comun divisore cercato") finisci.
Dimostrazione della correttezza dell'algoritmo
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
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
Riepilogo
Prospettiva
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
Riepilogo
Prospettiva
/* 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
}
/* 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)
@tailrec
def 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
a
end
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 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 (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);
}
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
}
Note
Bibliografia
Voci correlate
Altri progetti
Collegamenti esterni
Wikiwand - on
Seamless Wikipedia browsing. On steroids.