Abbiamo visto che il minimo comune multiplo (mcm) e il massimo comun divisore (MCD) di due numeri sono strettamente correlati; dati due numeri r e s, si ha che mcm(r,s) = rs/MCD(r,s). Ne consegue che basta avere un algoritmo per calcolare uno dei due valori, e siamo anche in grado di trovare l’altro; visto che il mcm è (di solito molto) maggiore del MCD, chiaramente è meglio dedicarci a quest’ultimo.
L’algoritmo più antico noto per calcolare il MCD di due numeri è così antico che non sono non c’era ancora il nome “algoritmo”, ma non credo la gente avesse in mente addirittura il concetto idi algoritmo. Lo si trova infatti in Euclide, che nei suoi Elementi non ha trattato solo di geometria ma anche dei numeri. L’algoritmo euclideo per calcolare MCD(r,s) è concettualmente molto semplice: se r=s, allora MCD(r,r)=r; altrimenti, supponendo che r>s, MCD(r,s)=MCD(r-s,s). Tutto qua. Il lettore più attento (occhei, il lettore meno attento ha già semsso di leggere da un po’) si sarà sicuramente accorto che il procedimento deve per forza terminare, visto che nel caso generale si passa da una coppia di numeri a una coppia la cui somma è minore, e non si può scendere all’infinito visto che la somma sarà sempre positiva. Non è nemmeno troppo difficile scoprire che in effetti l’algoritmo calcola correttamente il MCD di due numeri. Se i numeri sono uguali la cosa è immediata; altrimenti, se m è l’ancora incognito MCD(r,s), allora r=mh e s=mk; quindi m è sicuramente un fattore comune di r-s=m(h-k) e s=mk: e se ci fosse un fattore comune maggiore nella differenza, quel fattore ci sarebbe stato anche all’inizio.
La cosa più incredibile è che l’algoritmo che si usa oggi per calcolare il MCD di due numeri è ancora essenzialmente quello di Euclide! L’unica miglioria che c’è stata è che non si sottraggono più i due numeri ma si prende il resto della loro divisione e lo si sostituisce al maggiore dei due; se il minore divide esattamente il maggiore, allora il MCD cercato è il numero minore. E in effetti non è che cambi molto, visto che come certo ricordate la divisione tra numeri interi non è altro che una ripetuta serie di sottrazioni. L’algoritmo così modificato è molto veloce, richiedendo una quantità di operazioni dell’ordine del logaritmo dei numeri; il caso peggiore si ha quando i due numeri dati sono in posizioni successive della successione di Fibonacci… ma questa è un’altra storia, che forse prima o poi racconterò.
Termino con un simpatico problemino matematico (la parola “simpatico” sta ovviamente a indicare qualcosa che farà arrabbiare chi cercherà di risolverlo, e farà arrabbiare ancora di più chi leggerà la soluzione e scoprirà la semplicità). Ci sono due amiche, Thelma e Louise, che hanno preparato due pile di pancake e si accingono a mangiarle. Le amiche si alternano a prendere pancake dalla pila in quel momento più alta, togliendone un multiplo a piacere del numero presente nella pila più piccola. Visto che il pancake più in basso è sempre molliccio, la prima che è costretta a prenderlo ha perso il gioco. Se Thelma e Louise scelgono la loro migliore strategia, chi vincerà, data una coppia di valori iniziali? La risposta alla prossima puntata!

Ultimo aggiornamento: 2009-07-06 08:00