Thread: Binary Euclid's Algorithm

If your main goal here is reducing fractions, then you really don't anything more than the standard algorithm gcd(N,M) = gcd(M, N mod M). The binary version is a slight improvement over the original (based on your source) and I doubt it's really worth messing up (beyond curiosity). Consider:

Code:

#include <iostream.h>

int GCD(int N, int M)
{
	if (N % M == 0)
	{
		return M;
	}
	else
	{
		return GCD(M, N % M);
	}
}

int main()
{
	int numerator, denominator, g;
	cout<<"Numerator: ";
	cin>>numerator;
	cout<<"Denominator: ";
	cin>>denominator;
	g = GCD(numerator, denominator);
	cout<<endl<<numerator / g<<" / "<<denominator / g<<endl;
	return 0;
}

This should do everything you need it to. Alturnatively you could write

Code:

(N % M == 0)?(return M):(return GCD(M, N%M))

in place of the if-else statement