Euclid's Algorithm (Greatest Common Divisor)

Question

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.

1. Divide m by n and let r be the remainder.
2. If r is 0, n is the answer; if r is not 0, continue to step 3.
3. Set m = n and n = r. Go back to step 1.

Below is my implementation of this algorithm.

#include <stdio.h>
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?

• Radiodef: Well if r is never 0 and the loop never exits, blame Euclid.
• Jodrell: all integers are divisible by 1.
• user39545: 1. Implement Euclidean algorithm to find gcd of any N numbers.[ gcd(a,b), gcd(a,b,c), gcd(a,b,c,d) etc.]

Answer 1

Unlike Yuushi, I'm not too fond of recursions, at least when they are not really needed. This is one of those cases.

First, the negative input... The greatest common divisor of numbers -8 and -12 is 4, wouldn't you agree? So, instead of

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

I'd put

if (m < 0) m = -m;
if (n < 0) n = -n;

to ensure that both of the numbers are nonnegative. Btw, else rarely (if ever) makes sense after return.

Second, I think that breaking the loop

if (r == 0)
 break;

is misguiding, because what you really want to do is stop the function and return the result. In other words,

if (r == 0) return n;

Third, since your loop is technically infinite, then do { ... } while(true); is equivalent to while (1) { ... }. Personally, I find the latter to be more readable.

Lastly, true does not exist in standard C. If you really want to use it, then include stdbool.h. This belongs to the C99 standard (so, it doesn't work in C89/C90). Personally, I prefer 1 and 0, but this is probably a matter of habit.

• Shadur-don't-feed-the-AI: Here's the problem with do-while explained a little deeper.
• laindir: This will converge to zero regardless of sign, so it's possible to just abs the result: return n < 0 ? -n : n; ...I'm also more inclined to say while((r = m % n)), but that's more personal preference.
• Vedran Šego: @laindir I prefer working with the positive numbers, because there is a slight indeterminism with the negative ones: prior to C99, % was not uniquely defined for the negative numbers, and thus that depends on the compiler. I admit, it is highly unlikely to encounter such an old compiler, but doing one ?: instead of two if-s is, IMO, not worth it. As for your while, I like it as well, but such constructs tend to be confusing to the reader (who can easily confuse = with ==). Why the double parentheses?
• laindir: With Euclid's Algorithm (and probably other strictly mathematical uses of modulo--array indexing is not one), it doesn't matter whether your implementation of modulo is based on division rounding toward zero or toward negative infinity (which, as you correctly point out, is implementation defined in C89). Double parentheses is a habit I picked up by enabling all gcc warnings; it makes it explicit that the value of the assignment is used as an expression (and that the user didn't mean to write while(r == m % n)). You could more explicitly say while((r = m % n) != 0), but I find that noisy.

Answer 2

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.

• Fiddling Bits: Donald Knuth says that the algorithm I mentioned in my question is for positive numbers. Is there another, or expanded, algorithm for both positive and negative numbers?
• Michael Urman: Disagreed on using unsigned parameters for the scenario described. For the given code, I would consider just taking the absolute values inside the function.
• Yuushi: @MichaelUrman Sure, that's probably the better idea in this case. Using unsigned was more a way of showing the idea of being explicit in what parameters are actually allowed for the function as-is. I agree though, using abs would be the better solution.
• Yuushi: @Jodrell Yes? 0 is divisible by any number, hence gcd(a, 0) = a for all a. If you really want to get into the math of it...
• Yuushi: @Jodrell No. You have it mixed up. Nothing is divisible by 0, but 0 is divisible by everything.

Answer 3

Instead of the using the while(true) construct, it's clearer and readable to state a condition necessary for the loop to continue. Also, gcd is defined for negative integers as well and they can be handled easily.

The base condition is:

gcd(m, n) = gcd(n, m % n) when n != 0
 = m when n = 0

When both m and n are zero, then gcd is not defined and we return -1.

#include <stdio.h>
int gcd(int m, int n) {
 if (m == 0 && n == 0)
 return -1;
 if (m < 0) m = -m;
 if (n < 0) n = -n;
 int r;
 while (n) {
 r = m % n;
 m = n;
 n = r;
 }
 return m;
}

Answer 4

With this little code, it's more important to avoid inelegance than to try to display more elegance. (Unless you find recursion to be elegant, and as Yuushi shows, there's a decent argument for that.) So instead, I'm going to focus on non-code elegance.

Consider future readers of your function: include some of the documentation you presented for your question in your code. While GCD is certainly common enough around here, and a word for word explanation would match your code, a link or reminder can go a long way. Not all algorithms are familiar to everyone.

Consider also the users of your code: document what kinds of input the function accepts (apparently non-negative numbers) and what it does when provided inputs it does not accept (apparently it sometimes returns -1 instead of a GCD). This may help you remember to consider and thus normalize the behavior when one parameter is 0 and the other is negative. If calling code only has access to a header file, the implementation can't be cross-checked, so such cases deserve mention to enable the caller to perform error checking.

Answer 5

You don't include <stdbool.h> at the beginning of your code, even though you use a true value in a statement.

---

You never check if m and n are equal for an early exit.

---

Your condition statements are good from a readability standpoint, but could be simplified if you desired

if((m == 0) || (n == 0))
 return 0;
if(!m || !n) 
 return 0;

---

Instead of hardcoding values, I would allow input by the users for values during run-time.

int num1 = 600, num2 = 120; // not dynamic
int num1, num2;
printf("%s\n", "Input two numbers: ");
scanf("%d%d", &num1, &num2);
if(!isdigit(num1) || !isdigit(num2)) return -1; // check if input data are integers
...

---

Some people may argue to not have a break statement in your code, and to just return.

if(r == 0)
 return n;

I'm actually a fan of the break statement, because otherwise you have to keep track of another place you return from, which I don't like.

---

Use actual variable names instead of just letters.

int greatestCommonDivisor(int m, int n) // confusing in
int r; // later algorithms
int greatestCommonDivisor(int num1, int num2) // less
int remainder; // confusing

---

I like to put simple if statements all on one line, it helps me know that the if condition has only one statement and no braces.

if((m == 0) || (n == 0)) return 0;

• Yuushi: I disagree with the variables names. Here, m and n are fine; using num1 and num2 is no more readable.
• syb0rg: @Yuushi Here, maybe. In other places, probably not. It was just an example I gave. I'll edit in more useful names.

Answer 6

The whole algorithm can be broken down into one simple line (not including input sanity check). For speed, that line can be put into a loop if needed and completely do away with the overhead of a function call.

This also helps the compiler optimize by knowing where and how the loop will exit.

Is this readable? Ehh, probably not by less experienced coders but it is elegant...

#include <stdio.h>
unsigned int gcd(unsigned int m, unsigned int n)
{
 if(!m || !n)
 return(0);
 for(unsigned int r = m%n; r; m = n, n = r, r = m%n);
 return(n);
}
int main()
{
 printf("50, 5: %d\n", gcd(50,5));
 printf("5, 50: %d\n", gcd(5,50));
 printf("34534, 567568: %d\n", gcd(34534, 567568));
 return(0);
}

• Fiddling Bits: Very clever! I like it! That's basically what I've done, but used that nature of a for loop. Awesome!

Answer 7

Here is a simple recursive solution in C, this is pretty elegant.

Note* I used ternary operators for the boolean statements, Type it in on Google for more information and check out the wikipedia page for ternary operators in C

#include <stdio.h>
#include <stdlib.h>
// recursively computes gcd
int gcd(int a, int b) 
{
 return (b != 0)? gcd(b, a % b): a;
}
int main(int argc, char* argv[]) 
{
 // Specify values a and b or
 int a = 28, b = 7, result;
 // Run program with command line arguments
 result = (argc != 3)? gcd(a, b): gcd( atoi(argv[1]), atoi(argv[2]) );
 // print result
 printf("\n%d", result);
}

*And finally here it is in about every other language: http://rosettacode.org/wiki/Greatest_common_divisor*

• Jamal: Considering this is primarily an English website, most people wouldn't be able to understand that language. Your first code block and its explanation are okay, though.
• Nick Gallimore: Yeah I just put it in there when I came across it on rosettacode.org