Euclid's Algorithm (Greatest Common Divisor)

According to Donald Knuth in "The Art Of Computer Programming", the following is how to find the greatest common divisor of two positive numbers, m and n, using Euclid's Algorithm.

• Divide m by n and let r be the remainder.

• If r is 0, n is the answer; if r is not 0, continue to step 3.

• Set m = n and n = r. Go back to step 1.

Below is my implementation of this algorithm.

#include 

int greatestCommonDivisor(int m, int n)
{
    int r;

    /* Check For Proper Input */
    if((m == 0) || (n == 0))
        return 0;
    else if((m < 0) || (n < 0))
        return -1;

    do
    {
        r = m % n;
        if(r == 0)
            break;
        m = n;
        n = r;
    }
    while(true);

    return n;
}

int main(void)
{
    int num1 = 600, num2 = 120;
    int gcd = greatestCommonDivisor(num1, num2); 

    printf("The GCD of %d and %d is %d\n", num1, num2, gcd);

    getchar();
    return 0;
}

Though it appears to work just fine, it doesn't seem to be as elegant as I'd like, especially in the do-while loop. Also, the while(true) seems dangerous, though I'm pretty confident that r will be reduced to 0 eventually and we'll break out of the loop.

Do you have any suggestions on either making the code more elegant or robust?

Firstly, your implementation is (arguably) not quite correct:

else if((m < 0) || (n < 0))
     return -1;

The GCD of two negative numbers is perfectly well defined. However, if you really don't want the user to pass in negative numbers, make it explicit in the function signature:

unsigned greatestCommonDivisor(unsigned m, unsigned n)

Euclid's algorithm is one of the most basic examples of where recursion shines:

unsigned greatestCommonDivisor(unsigned m, unsigned n)
{
    if(n == 0) return m;
    return greatestCommonDivisor(n, m % n);
}

We first check the base case, which is 2: If r is 0, n is the answer; if r is not 0, continue to step 3. The recursive call actually combines steps 1 and 3 here: m % n sets n to be the remainder r, and we call the function again with n = m.

As a final note, a lot of people avoid recursive functions in C/C++ because most compilers don't optimise tail-calls to use constant stack space. However, Euclid's algorithm will perform only O(log N) steps, hence it's easy to see on any computer with (reasonable) stack size, this won't cause a stack overflow for numbers whose size is constrained by int or unsigned.

StackExchange Code Review Q#37189, answer score: 21