Calcolo del massimo comun divisore in C++
Il massimo comun divisore di due numeri interi non nulli è definito come il numero naturale più grande per il quale entrambe i numeri possono essere divisi, ad esempio $latex MCD(12,8) = 4 $.
Il massimo comun divisore gode di alcune proprietà, tra cui:
- $latex MCD(a, b) = MCD(-a, b) = MCD(a, -b) = MCD(-a, -b)$
- $latex MCD(a, 0) = |a|$
- $latex MCD(0, 0) $ non è definito
Un primo (inefficente) algoritmo per trovare il massimo comun divisore è quello che utilizza un intero che va da 1 a min(a, b) e controlla se questo intero divide i numeri in input, salvando il più grande intero trovato.
long mcd (long a, long b){ long divisore = 0; a = abs(a); b = abs(b); if (a==0 && b==0) throw "mcd(0,0) non è definito"; if(a==0) return b; if(b==0) return a; if (a > b) swap(a,b); for(long i = 1; i <= a; i++) { if( ( (a%i) == 0) && ( (b%i) == 0) ){ divisore = i; } } return divisore; }
Per migliorare l’efficienza dell’algoritmo possiamo utilizzare una proposizione che dice che se a e b sono due interi e c = a mod b, allora $latex MCD(a,b) = MCD(b, c)$.
L’algoritmo che ne risulta è detto Algoritmo di Euclide:
long mcd2 (long a, long b) { a = abs(a); b = abs(b); if (a==0 && b==0) throw "mcd(0,0) non è definito"; if(a==0) return b; if(b==0) return a; if (a < b) swap(a,b); long c = a % b; return mcd2(b,c); }
Ricorsivamente, richiamamo la funzione mcd2(b, a%b) fino a che c diventa zero.
L’algoritmo può essere migliorato ulteriormente eliminando la ricorsione e sostituendola con un ciclo while:
long mcd3 (long a, long b) { a = abs(a); b = abs(b); if (a==0 && b==0) throw "mcd(0,0) non è definito"; if(a==0) return b; if(b==0) return a; if (a < b) swap(a,b); long temp_a; long temp_b; while(b != 0){ temp_a = b; temp_b = a % b; a = temp_a; b = temp_b; } return a; }
Proviamo a testare i tempi di risposta degli algoritmi.
I due dati in input saranno 4.180.000 e 25.110.000. Il loro massimo comun divisore è 10.000.
Calcoleremo il massimo comun divisore 100.000.000 di volte con le due versioni dell’algoritmo di euclide e 1.000 volte con il primo algoritmo.
void calc(long a, long b, unsigned int times, long(*mcd_fun)(long,long)){ clock_t start, end; start = clock(); for(unsigned int i = 0; i < times; i++) mcd_fun(a,b); end = clock(); double elapsed = (end - start) / ((double)CLOCKS_PER_SEC); cout << times << " calcoli in: " << elapsed << " secondi" << endl; } int main() { calc(4180000,25110000, 100000000, mcd3); calc(4180000,25110000, 100000000, mcd2); calc(4180000,25110000, 1000, mcd); }
L’output, sulla mia macchina, è:
100000000 calcoli in: 11.343 secondi 100000000 calcoli in: 22.714 secondi 1000 calcoli in: 16.538 secondi
Come ci si aspettava, il primo algoritmo proposto è estremamente inefficiente.
L’algoritmo di Euclide risulta efficiente, in particolare la versione iterativa che opera in metà del tempo rispetto a quella ricorsiva.