6
\$\begingroup\$

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;
}
\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
7
  • 2
    \$\begingroup\$ I'm pretty sure that for any signed integer type T, then sizeof (unsigned T) == sizeof (T). 6.2.5.6 says "For each of the signed integer types, there is a corresponding (but different) unsigned integer type (designated with the keyword unsigned that uses the same amount of storage (including sign information) and has the same alignment requirements" (my emphasis). I'd still avoid that type-punning, though. \$\endgroup\$ – Toby Speight Apr 23 at 7:15
  • 5
    \$\begingroup\$ With optimization options enabled, the gcc compiler produces the very same code for while ((a = a % b)) { unsigned tmp = a; etc. and while ((tmp = a %b)) { .... So, don't worry to much about the number of assignments in the source code with execution speed in mind. Focus on simplicity and readability (which may be a reason to prefer the latter version). \$\endgroup\$ – Michel Billaud Apr 23 at 8:07
  • \$\begingroup\$ Which one do you mean by "the latter"? @MichelBillaud \$\endgroup\$ – j3141592653589793238 Apr 23 at 12:11
  • \$\begingroup\$ On x86, it's impossible to perform the inner loop with less than 4 registers: DIV takes divisor from EDX:EAX and writes quotient and remainder into EAX and EDX, and arguments are in EDI and ESI on function entry, so that's 4 in total. And doubling the code only makes it execute twice as much DIVs, so it's a guaranteed pessimization. \$\endgroup\$ – Joker_vD Apr 23 at 23:46
  • \$\begingroup\$ @Joker_vD I'm not following how that code would change the number of DIVs. Yes, there are two per iteration of the loop. But it tests after each one it does; i.e. it tests twice per loop and will jump out immediately. So that version would do the same number of DIVs as the other version (because it only does half as many loop iterations). Which seems irrelevant to the point that I was making, since I explicitly said not to use that code and instead let the compiler do it -- if the compiler found it a useful optimization. \$\endgroup\$ – mdfst13 Apr 24 at 5:36
5
\$\begingroup\$
#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.

\$\endgroup\$
3
  • \$\begingroup\$ Sorry, @mdfst13, I really don't understand what you're trying to say there. What "multi-line syntax" is weird? \$\endgroup\$ – Toby Speight Apr 23 at 8:18
  • \$\begingroup\$ Oh, just the continuation lines? I'm not sure what needs to be explained, given it's not a beginner question. \$\endgroup\$ – Toby Speight Apr 23 at 11:46
  • 1
    \$\begingroup\$ I'm alright with that as is! I don't think the continuation lines are specific to this question. But thanks! \$\endgroup\$ – j3141592653589793238 Apr 23 at 12:09
1
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.