Algoritmo di Euclide: differenze tra le versioni

Versione delle 08:46, 30 gen 2025

Versione attuale delle 13:09, 1 mag 2025

(Una versione intermedia di un altro utente non mostrate)

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