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.