Algoritmo di Euclide: differenze tra le versioni

Versione delle 08:31, 30 gen 2025

Versione attuale delle 13:09, 1 mag 2025

(2 versioni intermedie di 2 utenti non mostrate)

Riga 3:

{{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]] <math>a</math> e <math>b</math>, l'algoritmo prevede che si controlli se <math>b</math> è zero. Se lo è, <math>a</math> è il Minimo Comun Denominatore (MCD). Se non lo è, si

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.

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

Riga 10:

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 lal'operazione di divisione colcon 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.

Riga 19:

inizia

leggi (a, b)

mentrefinché b > 0 fai:

r <- mod(a, b)

a <- b