MCD e Ricorsione

Nel post dedicato all’MCD abbiamo ricondotto le operazioni sugli interi ad operazioni sugli insiemi:

• moltiplicazione tra interi / unione di insiemi di fattori
• divisione tra interi / differenza di insiemi di fattori
• MCD tra interi / intersezione di fattori

E’ una formalizzazione molto compatta che consente di eseguire diversi calcoli sui numeri primi senza necessariamente ripetere un numero considerevole di divisioni. Sin ora, però, abbiamo definito e determinato le proprietà dell’MCD, ma non abbiamo fornito alcun algoritmo per calcolarlo. Ricordate ? Abbiamo parlato degli algoritmi tempo addietro.

Riassumiamo ciò che sappiamo dell’MCD:

• l’MCD è dato dai fattori comuni di due numeri
• l’MCD di un numero e di sé stesso è uguale allo stesso numero

Usiamo ora una notazione più breve per descrvire le stesse proprietà, introducendo una funzione di due interi, MCD(A,B). Sappiamo già che MCD(A,A) = A e usiamo una osservazione per determinare una proprietà che si rivelerà molto utile. Abbiamo detto che i fattori di un intero sono elencabili come un insieme, supponiamo che l’insieme dei fattori di A e di B siano dati da:

F(A) = {A1 M A2}
F(B) = {B1 M B2}

dove A1, A2, B1, B2 sono insiemi di fattori non comuni, ed M è l’insieme dei fattori comuni di A e B, cioé il massimo comun divisore, ciò che stiamo cercando. Supponiamo ora che A sia maggiore di B, e calcoliamo l’MCD di A-B e di B:

MCD(A-B,B) = MCD (A1 x M x A2 – B1 x M x B2, B1 x M x B2) =

= MCD (M x (A1xA2 – B1xB2), B1 x M x B2 ) = M

Facciamo un esempio pratico e calcoliamo l’MCD di 18-12 e di 12:

MCD(18-12,12) = MCD(2x3x3-2x2x3, 2x2x3) = MCD(2x3x(3-2), 2x2x3) = 2×3 = 6

nell’esempio, 2×3 è la serie di fattori comuni di 12 e 18, l’MCD appunto, che resta comune anche calcolando la differenza dei due numeri.

E’ una proprietà molto interessante:

MCD(A, B) = MCD (A-B, B)

l’MCD di due numeri è pari all’MCD della loro differenza.

Perché è interessante ? Perché se continuiamo a sottrarre due numeri l’uno dall’altro si arriva invariabilmente allo stesso numero, al primo e al secondo argomento. Proviamo:

MCD(18,12) = MCD(18-12, 12) = MCD(6, 12) = MCD(6, 12-6) = MCD(6,6)

ma noi sappiamo già che MCD(N, N) = N, quindi:

MCD(18,12) = 6

Abbiamo trovato, quindi, un modo di calcolare il Massimo Comun Divisore di due numeri senza divisione, ma ripetendo una serie di sottrazioni (chi di voi pensa che stiamo “barando” ha perfettamente ragione: una divisione è, in effetti, una serie di sottrazioni).

L’algoritmo per il calcolo dell’MCD che abbiamo costruito è ricorsivo (ne abbiamo già parlato) e si scrive in due righe semplici semplici:

MCD(N,N) = N

MCD(N, M) = MCD(N-M, M)

elegante, no ?

Euclide, due millenni e mezzo fa, è stato più astuto di noi e ha trovato una formulazione del calcolo dell’MCD, oggi nota come Algoritmo di Euclide, ben più veloce della nostra. Inoltre, ad essere rigorosi, dovremmo ancora aggiungere un paio di cosine al nostro lavoro: dimostrare l’algoritmo per induzione matematica e accertarci che termini per N, M qualsiasi.

Ovviamente, ci torneremo.