Euclidean algorithm to determine GCD (greatest common divisor) in C — alternative method

Question

Been looking into some simple algorithms, I came up with the following piece of code in C to implement the Euclidean algorithm iteratively (I like to be clear here, I don't want the recursive implementation for now).

I've seen various other implementations and in fact most books prefer a different pseudo code.

I'm wondering if the following implementation is any better or worse?

#include <stdlib.h>


void swap_numbers(void *a, void *b)
{
  int temp = *(int *)a;
  *(int *)a = *(int *)b;
  *(int *)b = temp;
}

unsigned euklid_iterative(unsigned a, unsigned b)
{
  while ((a = a % b))
    swap_numbers(&a, &b);
  return b;
}

Answer 1

Unnecessary function calls

My quick thought is that you are making an unnecessary function call.

unsigned temp;
while ((temp = a % b)) {
    a = b;
    b = temp;
}

The thing with the doubled parentheses is a hack to keep some compilers from warning you that you may be doing an unintentional assignment. It should make no functional difference.

This does fewer assignments. Three compared to four in your version. And it makes no function calls. Typically a function call is more involved than an assignment. Because it has to first save the current state, then jump somewhere else and do work, and finally restore the original state. The save and restore steps themselves often involve assignments. And those may be relatively expensive assignments from register to cache or memory. Whereas that loop can be done with three registers (or even two if the compiler optimizes out temp by doubling the code).

while ((a = a % b)) {
    if (!(b = b % a)) {
        return a;
    }
}

No temp in that version, but duplicate logic. I wouldn't normally recommend writing that code. But it would be a perfectly legitimate compiler optimization if there is a shortage of available registers.

Note: if you only call this function a few times, this won't make a difference. Use whatever you find more readable. But if you are calling GCD in your main loop, it is possible that efficiency will matter. If efficiency does matter, my revised version (the first one) will (absent compiler optimizations) probably be faster than your version. While premature optimizations are to be avoided, there is little harm in picking the more efficient version if you have two working versions. And GCD is exactly the kind of problem that may be subject to profiling that would lead to that kind of optimization. So many sources may offer the best optimized algorithm rather than an alternative.

I find it a best practice to never use the statement form of control structures and always use the block form. I also prefer the brackets on the same line as the control structure. The latter is very much opinion, but the former is based on actual experience with bugs caused by editing.

Be careful of types

I also find it a bit risky that your variables are unsigned in the original function but int in the swap_numbers function. This presumably works because the unsigned and int types use the same storage width. But that's an implementation detail. Is that implementation detail guaranteed always? I don't know off-hand. Perhaps you already did that work and do know. But you don't say that you know and there's no comment explaining when you can and cannot use swap_numbers.

For example, what would happen if used with an unsigned long? On some systems, that might work because int and long are the same width. On other systems, you may only swap part of the numbers. Possibly only some of the time (because if the bytes that you are swapping happen to be the ones with data, it might not matter).

You might fix this by switching from pointers to handles (pointers to pointers).

void swap_numbers(void **a, void **b)
{
  void *temp = *a;
  *a = *b;
  *b = temp;
}

unsigned euklid_iterative(unsigned *a, unsigned *b)
{
  while ((*a = *a % *b))
  {
    swap_numbers(&a, &b);
  }

  return *b;
}

But it might be easier just to write a swap_unsigned function. Or write out the swap entirely as I did originally.

All code in this post is untested. Not even for compilable syntax much less correct logic. Use at your own risk.

Answer 2

#include <stdlib.h>

This is not required - we use nothing declared by that header.

void swap_numbers(void *a, void *b)
{
  int temp = *(int *)a;

Avoid void! We don't need to erase and reinstate type information like that:

static void swap_unsigned(unsigned *a, unsigned *b)
{
  unsigned temp = *a;
  *a = *b;
  *b = temp;
}

If we'll need this for several types, we could use a preprocessor macro to help us create the functions:

#define MAKE_SWAP_FUNCTION(type, name)          \
    static void swap_name(type *a, type *b)     \
    {                                           \
        type temp = *a;                         \
        *a = *b;                                \
        *b = temp;                              \
    }

MAKE_SWAP_FUNCTION(unsigned int, unsigned)
MAKE_SWAP_FUNCTION(long double, long_double)
/* etc. */

#undef MAKE_SWAP_FUNCTION

Or just replace the function with a macro:

#define SWAP_VALUES(type, a, b)                 \
    {                                           \
        type temp = a;                          \
        a = b;                                  \
        b = temp;                               \
    }

Or, as suggested in the other answer, simply code the swap directly in the main function.

Answer 3

if the following implementation is any better or worse?

Consider 0

GCD(a,b) is usually considered communicative: GCD(a,b) == GCD(b,a).

while ((a = a % b)) is OK when a==0, yet undefined when b==0.

---

No swap

Rather than spend time swapping, just add a little more code.

unsigned gcd_no_swap(unsigned a, unsigned b) {
  while (a) {
    b %= a;
    if (b == 0) return a;
    a %= b;
  }
  return b;
}

When /, % is expensive

A solution without /, % may run faster when such repetitive operations are expensive.

unsigned gcd_no_div(unsigned a, unsigned b) {
  int shift;

  // GCD(0,b) == b; GCD(a,0) == a, GCD(0,0) == 0
  if (a == 0) {
    return b;
  } else if (b == 0) {
    return a;
  }

  // find common power 2
  for (shift = 0; ((a | b) & 1) == 0; shift++) {
    a >>= 1;
    b >>= 1;
  }

  // Adjust so a is odd.
  while ((a & 1) == 0) {
    a >>= 1;
  }

  do {
    // Adjust so b is odd.
    while ((b & 1) == 0) {
      b >>= 1;
    }

    // a and b are both odd here.
    
    // Swap if necessary so a <= b,
    if (a > b) {
      unsigned t = b;
      b = a;
      a = t;
    }  // Swap a and b.

    b -= a;  // Here b >= a.
  } while (b != 0);

  return a << shift;  // Restore power-of-2 factor
}

---

Courtesy test harness

unsigned gcd_utest(unsigned m, unsigned n) {
  unsigned g1 = gcd_no_div(m, n);
  unsigned g2 = gcd_no_swap(m, n);
  if (g1 != g2) {
    printf("Differ %u %u --> %u %u\n", m, n, g1, g2);
    exit(-1);
  }
  //printf("%u %u --> %u %u\n", m, n, g1, g2);
  return g1;
}

unsigned gcd_utests() {
  unsigned a[] = {0, 1, 2, UINT_MAX - 2, UINT_MAX - 1, UINT_MAX};
  unsigned n = sizeof a / sizeof *a;
  for (unsigned i = 0; i < n; i++) {
    for (unsigned j = 0; j < n; j++) {
      gcd_utest(a[i], a[j]);
    }
  }
  for (unsigned i = 0; i < 1000; i++) {
    gcd_utest(rand(), rand());
  }
  return 0;
}