Algoritmo di Euclide: differenze tra le versioni

Versione delle 20:36, 25 lug 2018

Versione attuale delle 13:09, 1 mag 2025

(47 versioni intermedie di 42 utenti non mostrate)

Riga 1:

L''''algoritmo di Euclide''' è un [[algoritmo]] per trovare il [[massimo comun divisore|massimo comune divisore]] (indicato di seguito con MCD) tra due [[numero intero|numeri interi]]. È uno degli algoritmi più antichi conosciuti, essendo presente negli ''[[Elementi (Euclide)|Elementi]]'' di [[Euclide]]<ref>{{en}} [[Thomas LF. Heath]]Acerbi, ''The Thirteen Books of Euclid's Elements'', 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, [[Dover Publications]]</ref> intorno al [[300 a.C.]]; tuttavia, probabilmente l'algoritmo non è stato scoperto da [[Euclide]], maTutte potrebbele 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 (Aristotele)|I topici]]opere'', 158b2007, 29-35. L'algoritmo non richiede la [[fattorizzazioneBompiani]] dei due interi.

{{en}} [[Thomas L. Heath]], ''The Thirteen Books of Euclid's Elements'', 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, [[Dover Publications]]</ref> 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 ''[[Topici|I topici]]'', 158b, 29-35. L'algoritmo non richiede la [[fattorizzazione]] dei due interi.

Dati due [[numero naturale|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 [[Algoritmo ricorsivo#Ricorsione in coda|ricorsione in coda]].

Dati due [[numero naturale|numeri naturali]] <math>a</math> e <math>b</math>, l'algoritmo prevede che si controlli se <math>b</math> è zero. Se lo è, <math>a</math> è il MCD. Se non lo è, si

Tenendo nota dei quozienti ottenuti durante lo svolgimento dell'algoritmo, si possono determinare due interi ''p'' e ''q'' tali che ''ap''&nbsp;+&nbsp;''bq''&nbsp;=&nbsp;MCD(''a'',&nbsp;''b'').

deve dividere <math>\frac{a}{b}</math> e definire <math>r</math> come il resto della divisione (operazione indicata con "a modulo b" più sotto). Se <math>r=0</math> allora si può affermare che <math>b</math> è il MCD cercato, altrimenti occorre assegnare <math>a'=b</math> e <math>b'=r</math> e ripetere nuovamente la divisione.

Questo è noto con il nome di [[algoritmo di Euclide esteso]].

L'algoritmo può essere espresso in modo naturale utilizzando la [[Algoritmo ricorsivo#Ricorsione in coda|ricorsione in coda]].

Tenendo nota dei quozienti ottenuti durante lo svolgimento dell'algoritmo, si possono determinare due interi <math>p</math> e <math>q</math> tali che <math>ap+bq=MCD(a,b)</math>.

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 [[polinomio|polinomi]] ad una indeterminata su un [[campo (matematica)|campo]] ''K'', o polinomi omogenei a due indeterminate su un campo, o gli [[intero gaussiano|interi gaussiani]]. Un oggetto algebrico in cui è possibile eseguire la divisione col resto è chiamato [[anello euclideo]].

Questo è noto con il nome di [[Algoritmo esteso di Euclide|algoritmo di Euclide esteso]].

Questi algoritmi possono essere usati, oltre che con i [[numeri interi]], in ogni contesto in cui è possibile eseguire l'operazione di divisione con resto. Ad esempio, l'algoritmo funziona per i [[polinomio|polinomi]] ad una indeterminata su un [[campo (matematica)|campo]] ''K'', o polinomi omogenei a due indeterminate su un campo, o gli [[intero gaussiano|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:

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<ref>{{Cita web|url=https://www.treccani.it/enciclopedia/algoritmo-di-euclide_(Enciclopedia-della-Matematica)/|titolo=Euclide, algoritmo di - Treccani|sito=Treccani|lingua=it|accesso=2023-12-27}}</ref>:

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 ''<math>a''</math> e ''<math>b''</math> interi positivi assegnati, e sia ''<math>d''</math> il loro MCD.

Definiamo la successione di ricorrenza corrispondente ai passi dell'algoritmo di Euclide: ''a''<submath>0a_0 =a</submath> = ''a'', ''b''<submath>0b_0=b</submath> ''= b'', ''a''<submath>a_{n+1</sub>}=''b<sub>nb_n</submath>'', e ''b''<submath>b_{n+1}</submath> è il resto della divisione di ''a''<submath>na_n</submath> per ''b''<submath>nb_n</submath>, cioè ''a''<sub>n</submath>a_n = ''q''_n''b''_n q_nb_n+ ''b''<sub>b_{n+1}</submath>.

Per definizione di resto nella divisione, ''b''<submath>b_{n+1}<b_n</submath> <per ogni ''b''<submath>n</submath> per ogni ''n'', quindi la successione dei ''b''<submath>nb_n</submath> è strettamente decrescente, e quindi esiste un ''<math>N''</math> tale che ''b''<submath>Nb_N=0</submath> = 0.

Vogliamo dimostrare che ''<math>d'' = ''a''<sub>Na_N</submath>.

Infatti, per induzione si ha per ogni ''<math>n''</math> che ''<math>d'' | ''a''_na_n = ''b''_{b_{n-1}} = ''a''_{a_{n-2}} - ''q''_{q_{n-2}''b''<sub>}b_{n-2}</submath>. Inoltre, sempre per induzione, ''a''<submath>Na_N</submath> divide ''a''<submath>na_n</submath> per ogni ''<math>n'' ≤\le ''N''</math>, quindi divide anche ''b''<submath>nb_n</submath> per ogni ''<math>n'' < ''N''</math>, quindi ''a''<submath>Na_N=d</submath> = ''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-grande|''O''(''n)'')]] divisioni, dove ''<math>n''</math> è 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 ''<math>n''</math> cifre. Allora il tempo di calcolo reale è quindi ''<math>O''(''n''²^2)</math>.

Questo tempo è comunque considerevolmente migliore rispetto all'algoritmo euclideo originale, in cui l'operazione di modulo è effettuata mediante ripetute sottrazioni in ''<math>O''(2<sup>''^n'')</supmath>) passi. Di conseguenza, questa versione dell'algoritmo richiede un tempo pari a ''<math>O''(''n2^n''2<sup>''n'')</supmath>) per numeri con ''<math>n''</math> cifre, o ''<math>O''(''m''\log ''m'')</math> per il numero ''<math>m''</math>.

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 [[Sistema numerico binario|rappresentazione binaria]] dei computer per evitare le divisioni e quindi aumentare l'efficienza, sebbene anch'esso sia dell'ordine di ''<math>O''(''n''²^2)</math>: 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 ''<math>a''</math> e ''<math>b''</math> sono proprio i numeri che compaiono nella rappresentazione in [[frazione continua]] della frazione ''<math>\frac{a''}{b}</''b''math>. Si prenda l'esempio di ''<math>a''&nbsp;=&nbsp;1071</math> e ''<math>b''&nbsp;=&nbsp;1029</math> usato prima. Questi sono i calcoli con i quozienti in evidenza:

:<math>1071 = 1029 ×\times '''\mathbf{1'''} + 42</math>

:<math>1029 = 42 ×\times '''\mathbf{24'''} + 21</math>

:<math>42 = 21 ×\times '''\mathbf{2'''} + 0</math>

Da questo elenco si può vedere che

:<math>\frac{1071}{1029} = \mathbf{1} + \frac{1}{\mathbf{24} + \frac{1}{\mathbf{2}}}</math>.

Questo metodo può anche essere usato per valori di ''<math>a''</math> e ''<math>b''</math> [[numero reale|reali]]; se ''<math>\frac{a''}{b}</''b''math> è [[numero irrazionale|irrazionale]] allora l'algoritmo euclideo non ha termine, ma la sequenza di quozienti che si calcola costituisce sempre la rappresentazione (ora infinita) di ''<math>\frac{a''}{b}</''b''math> in frazione continua.

==Codici==

{{C|Controllare se i codici vanno mantenuti o trasferiti ad un altro progetto|informatica|giugno 2015}}

[[C (linguaggio di programmazione)|C]] e [[C++]] (algoritmo iterativo)

<sourcesyntaxhighlight lang="Cc" line="1">

/* Algoritmo iterativo */

int Euclide(int a, int b) // prototipo della funzione Euclide //

int euclide(int a, int b)

{

int r; // resto della divisione

while(b != 0) //ripetereripete finché non riduciamoriduce 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; //scambiamo ilin ruolob diora c'è r = a e% b

}

return a; //... e quando b è (o è diventato) 0, il risultato è in a

}

</syntaxhighlight>

</source>

[[C (linguaggio)|C]] e [[C++]] (algoritmo ricorsivo)

[[MATLAB]]

<syntaxhighlight lang="c" line="1">

/* Algoritmo ricorsivo */

int euclide(int a, int b)

{

if(b == 0)

return(a);

else

return euclide(b, a % b); // la funzione richiama sé stessa

}

</syntaxhighlight>

[[Scala (linguaggio di programmazione)|Scala]] (algoritmo ricorsivo)

<source lang="Matlab">

<syntaxhighlight lang="scala" line="1">

function out= miogdc (a,b)

@tailrec

if(b==0)

def euclide(a: Int, b: Int): Int =

out=a;

if (b == 0)

elseif(b==1) a

out=1;

else

out=miogdceuclide(b,mod( a, % b));

</syntaxhighlight>

[[MATLAB]] (algoritmo iterativo)

<syntaxhighlight lang="matlab" line="1">

function out = euclide(a, b)

if(b == 0)

out = a;

elseif(b == 1)

out = 1;

else

out = euclide(b, mod(a,b));

end

end

</syntaxhighlight>

</source>

[[Python]]

[[Python]] (algoritmo iterativo)

<source lang="Python">

<syntaxhighlight lang="python" line="1">

def MCD(a,b):

def euclide(a, b):

while b != 0:

while b:

a, b = b, a % b

return a

</syntaxhighlight>

</source>

[[Ruby (linguaggio di programmazione)|Ruby]] (algoritmo iterativo)

[[Ruby]]

<syntaxhighlight lang="ruby" line="1">

<source lang = "Ruby">

def euclide(a, b)

while( b != 0) do

a, b = b, a % b

end

return a

end

</syntaxhighlight>

</source>

[[Pascal (linguaggio di programmazione)|Pascal]] (algoritmo iterativo)

<sourcesyntaxhighlight lang="Pascalpascal" line="1">

function MCDeuclide(a, b: integer): integer;

var
r: integer;

begin

if b = 0 then

MCD := a

else begin

r:=(a mod b);begin

while not ( r := 0)(a domod b);

while not (r = 0) do

begin

begin

a:=b;

b a :=r b;

r:=(a mod b) := r;

r := (a mod b);

end;

end;

MCD:=b

MCD := b;

end;

end;

end;

</syntaxhighlight>

</source>

[[BASIC]] (vb.net, algoritmo iterativo)

<sourcesyntaxhighlight lang="vbnet" line="1">

Function Euclide(ByVal a As Int16, ByVal b As Int16) As Int16

Dim r As Int16 = a Mod b

While (r <> 0)

Function Euclide_MCD(ByVal a As Int16, ByVal b As Int16) As Int16

a = b

b = r

r = a Mod b

Wend

Return b

Dim r As Int16 = a Mod b

End Function

</syntaxhighlight>

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.

While (r <> 0)

a = b

b = r

r = a Mod b

End While

[[PHP]] (algoritmo iterativo)

Return b

<syntaxhighlight lang="php" line="1">

function euclide($a, $b) {

End Function

while ($b) {

</source>

list($a, $b) = array($b, $a % $b);

}

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.

return $a;

[[PHP]]

<source lang="PHP">

function mcd($a,$b) {

while($b) list($a,$b)=array($b,$a%$b);

return $a;

}

</syntaxhighlight>

[[Java (linguaggio di programmazione)|Java]] (algoritmo iterativo)

</source>

<syntaxhighlight lang="java" line="1">

private static int euclide(int a, int b) {

[[Go (linguaggio di programmazione)|Go]]

int r;

<source lang="Go">

func mcd(a, while (b int)!= int0) {

for b ! r = 0a {% b;

a, b = b, a % b;

b = r;

}

return Math.abs(a);

}

</syntaxhighlight>

[[Rust (linguaggio di programmazione)|Rust]]<ref>{{Cita web|url=https://github.com/ProgrammingRust|titolo=Programming Rust|sito=GitHub|lingua=en|accesso=2023-01-06}}</ref> (algoritmo iterativo)

return a

<syntaxhighlight lang="rust" line="1">

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

}

</syntaxhighlight>

[[Go (linguaggio di programmazione)|Go]] (algoritmo iterativo)

</source>

<syntaxhighlight lang="go" line="1">

func euclide(a, b int) int {

for b != 0 {

a, b = b, a%b

}

return a

}

</syntaxhighlight>

==Note==

Line 159 ⟶ 216:

*[[Minimo comune multiplo]]

*[[Massimo comun divisore]]

*[[Algoritmo esteso di Euclide]]

*[[Equazione diofantea lineare]]

*[[Ritmo di Euclide]]

*[[Identità di Bézout]]

==Altri progetti==

{{interprogetto|commons=Category:Euclidean algorithm|preposizione=sull'}}

==Collegamenti esterni==

* {{Collegamenti esterni}}

*{{en}} [http://www.cut-the-knot.org/blue/Euclid.shtml Euclid's Algorithm] su cut-the-knot

* {{FOLDOC|Euclid's Algorithm|Euclid's Algorithm}}

*{{en}} [http://www.cut-the-knot.org/blue/binary.shtml Binary Euclid's Algorithm (Java)] su cut-the-knot

*{{en}} [httphttps://www.cut-the-knot.org/blue/EuclidAlgEuclid.shtml Euclid's Game (Java)Algorithm] su cut-the-knot

*{{en}} [https://www.cut-the-knot.org/blue/binary.shtml Binary Euclid's Algorithm (Java)] su cut-the-knot

*{{en}} [https://www.cut-the-knot.org/blue/EuclidAlg.shtml Euclid's Game (Java)] su cut-the-knot

{{Algebra}}

Line 175 ⟶ 236:

{{Portale|matematica}}

[[Categoria:Algoritmi numericiaritmetici|Euclide]]

[[Categoria:Euclide]]