Algoritmo di Euclide
A cosa serve?
L'algoritmo di Euclide calcola il massimo comune divisore (MCD) di due numeri interi.
Come funziona l'algoritmo di Euclide
Dati due interi a e b che rispettano la seguente condizione
$$ a \ge b \ge 0 $$
L'algoritmo effettua la divisione a:b e ne calcola il resto r.
$$ a:b = q \:\: \text{con r} $$
ossia
$$ a = qb + r $$
Se il resto è un intero positivo, divide b per r e ne calcola il resto.
$$ b:r = q_2 \:\:\text{con r} $$
L'algoritmo termina quando il resto è nullo ( r=0 ).
L'ultimo resto non nullo del processo è il Massimo Comune Divisore ( o MCD )dei due numeri.
Un esempio pratico
Dati due numeri a=48 e b=32
I due numeri rispettano la condizione
$$ a \ge b \ge 0 \\ 48 \ge 24 \ge 0 $$
Calcolo la divisione a:b
$$ 48:32 = 1 \:\:\text{con resto 16} $$
Il resto è diverso da zero (r=16)
Quindi calcolo la divisione b:r
$$ 32:16 = 2 \:\:\text{con resto 0} $$
Il resto è zero.
L'ultimo resto non nullo rpr=16 (il resto della precedente divisione) è il massimo comune divisore di 48 e 32.
$$ MCD(48,32)=16 $$
Ho così trovato il massimo comune divisore dei due numeri interi.
Quanti passi necessitano per trovare la soluzione
L'algoritmo di Euclide trova il massimo comune divisore MCD(a,b) di due numeri interi a e b in al massimo b passi.
Il numero intero b fissa un limite superiore al di sopra del quale non si può andare.
Tuttavia, si tratta di una stima in eccesso e non è la migliore possibile.
Esempio
Il precedente esempio MCD(48,32) richiede al massimo 32 passi.
Si tratta però di una stima troppo eccessiva.
Secondo il Teorema di Lamé i passi dell'algoritmo euclideo per calcolare il massimo comune divisore di due interi a e b è minore uguale a 5k. Dove k sono il numero di cifre dell'intero b.
Esempio
Il precedente esempio MCD(48,32) richiede al massimo 5*k passi
$$ 5 \cdot k \:\: passi $$
L'intero b ha due cifre (k=2)
$$ 5 \cdot 2 = 10 \:\: passi $$
La stima fornita dal teorema di Lamé è senza dubbio più vicina alla realtà.
E così via.
