Algoritmo MCD di Euclide

Non so se ne sei consapevole, ma in un articolo recente ho trattato in breve alcuni tra gli algoritmi antichi che ritengo più interessanti. Tra questi c’era anche l’algoritmo per ricavare l’MCD di Euclide.

Algoritmo mcd euclide

L’articolo di cui ti sto parlando è il seguente: ALLA SCOPERTA DI ALGORITMI ANTICHI E CURIOSI

Siccome ritengo che questo sia molto importante ed interessante, ho pensato di approfondirlo in un articolo a parte. Se sei iscritto alla newsletter lo sapevi già, se non sei ancora iscritto ti prego di farlo così potremo rimanere in contatto e ti aggiornerò su collaborazioni, news e ti fornirò settimanalmente contenuti riservati.

Ti basta lasciarmi la tua mail qui sotto:

Iscriviti alla nostra newsletter :


Intanto, per iniziare, ti rinfresco l’algoritmo di cui andremo a parlare (è espresso in pseudocodifica, una via di mezzo tra il linguaggio normale e il codice che andresti a scrivere in un linguaggio di programmazione formale).
Algoritmo MCD di Euclide:

a,b naturali

finchè a!=b (!= significa diverso):

se a>b allora a=a-b

altrimenti b=b-a

risultato a

Prima di proseguire la lettura, ti consiglio di provare a trovare una risposta alle seguenti domande:

  1. Come faccio ad ottenere l’MCD eseguendo delle sottrazioni?
  2. E’ più veloce questo metodo o quello dei divisori comuni che insegnano a scuola?

Algoritmo mcd euclide

Bene, spero che tu ci abbia pensato almeno un momento. Se ci arrivi da solo a queste risposte, di sicuro sarà più difficile dimenticarsele 😉

Comunque, ora ti darò una risposta che spero ti soddisfi.

Questo algoritmo sostanzialmente si basa su una proprietà dei numeri interi ossia:

Se due numeri sono divisibili per un terzo numero , allora anche la loro differenza lo sarà.

Questo è dimostrabile facilmente, qui sotto ti ho scritto in due righe il perchè ciò è vero:

Divisibilità differenza

E ciò spiega il perchè calcolare l’MCD tra sia lo stesso che trovarlo tra a-b o viceversa.

Per chi se ne intende già un po’ di programmazione e conosce il significato di ricorsione penso sia già evidente come dopo l’introduzione di questa proprietà si possa scrivere:

MCD (a,b)  = MCD (a-b,b) = MCD (a, b-a)

Evidentemente ora il segreto che si cela dietro l’algoritmo si chiarisce. Infatti attraverso sottrazioni ripetute, si arriva alla negazione della condizione finchè a!=b . Ossia si arriva necessariamente ad un momento in cui a=b, ossia si ha differenza nulla. A questo punto vuol dire che sia il primo che il secondo numero sono divisibili per a, che è quindi il nostro MCD.

Spero di aver risposto coerentemente alla prima domanda e di averti chiarito il perchè questo algoritmo funzioni. Se hai dubbi, critiche o suggerimenti lascia pure un commento o contattami.

Passiamo ora alla seconda domanda. Te la rinfresco:

E’ più veloce questo metodo o quello dei divisori comuni che insegnano a scuola?

Bene, certamente questo algoritmo non è dei più veloci se si devono trattare due numeri che si discostano di molto l’uno dall’altro. Prova a pensare a quante sottrazioni devi fare per trovare l’MCD tra 10000 e 30, procedendo con questo metodo. Per porre rimedio a ciò, esiste una versione che invece della sottrazione utilizza la divisione ed il  resto. Te lo lascio ricercare da solo, se avessi problemi nel comprenderlo contattami pure.

Certamente questo algoritmo è però conveniente nel caso si abbiano numeri vicini, in quanto con le sottrazioni si può risalire facilmente al divisore massimo comune.

Da un punto di vista del numero di operazioni che questo algoritmo deve eseguire, si può dire che nel caso peggiore debba eseguire operazioni, dove n=max(a,b).

Detto ciò, non so quanto convenga l’algoritmo che sfrutta il calcolo dei divisori primi comuni, anche dopo opportune ottimizzazioni.

Infatti analizzando le operazioni che in tal caso vanno eseguite, spesso è più efficiente qualche altro algoritmo per l’MCD, tra cui anche questo di Euclide.

Si devono infatti analizzare tutti i numeri che vanno da 2 a sqrt(a), tutti i numeri che vanno da 2 a sqrt(b). Si guarda se dividono a e b. Si deve ricercarne il massimo.

Ovviamente è possibile ottimizzarlo in vari modi, dato che in queste due righe ho solo ridotto il controllo alla radice del numero. Tuttavia lascio a te un’analisi ulteriore, in rete puoi trovare una valanga di materiale.

Infine mi sembra evidente che non venga presentato l’algoritmo per l’MCD di Euclide alle elementari o alle medie (se non per sorprendere gli studenti) dato che non è facilmente comprensibile il perchè funzioni. Inoltre con il metodo principalmente conosciuto si possono introdurre parecchi concetti utili! 🙂

Bene, il mio articolo termina qui. Spero di essere stato sufficientemente chiaro. In caso di dubbi sono qui.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *