GCD as fast as possible!

Hello! I have found this GCD (Greatest Common Divisor) algorithm and wonder if someone knows an even more efficient one? The faster the better.

Code:

int		gcd( int a, int b ) {
	int		t;
	
	if ( a < 0 )
		a = -a;
	
	if ( ! b )
		return a;
	
	if ( b < 0 )
		b = -b;
	
	if ( ! a )
		return b;
	
	t = 0;
	
	while ( ! ( ( a | b ) & 1 ) ) {
		a >>= 1;
		b >>= 1;
		++t;
	}
	
	while ( ! ( a & 1 ) )
		a >>= 1;
	
	while ( ! ( b & 1 ) )
		b >>= 1;
	
	while ( a != b ) {
		if ( a > b ) {
			a -= b;
			
			do {
				a >>= 1;
			} while ( ! ( a & 1 ) );
		}
		
		else {
			b -= a;
			
			do {
				b >>= 1;
			} while ( ! ( b & 1 ) );
		}
	}
	
	return a << t;
}

P.S. I indent with a tab length of 4 spaces in my environment, but here a tab is 8 spaces . Can I fix this with some setting? Would be nice. Thanks!!

Well my version is about 8 lines long but I am not going to bother seeing if it is more efficient than yours. Somehow this smells a little bit like someone's homework. There is a chance of fixing the tab on yours, but if you don't tell us what editor you are using its pretty tough to help.

There's a couple really fast solutions. Both are based upon the Euclidean Algorithm.

Method 1: Euclidean Algorithm at its finest.

Given an integer a, and an integer b, gcd(a,b)=d will be the last non-zero remainder of a set of equations resulting from the division algorithm. If a does divide b (as in a%b == 0) then the GDC is abs(b).

Code:

a  = b*q1  + r1    0<=r1<abs(b).
b  = r1*q2 + r2    0<=r2<r1.
r1 = r2*q3 + r3    0<=r3<r2.

Hopefully you notice a pattern here, let's see it in action.

-------------------------------------------------------------
For example, gcd(106,4).

If we divide 106 and 4 using the division algorithm, we get:

Code:

106 = 4*26 + 2
4   = 2*2  + 0

Therefore GCD(106,4) = 2.

This can be represented very easily in a recursive situation, as each iteration is dependant upon the previous iteration.

When I benchmarked this method, it ran on average 2x faster than the solution you posted. There are, of course, ways to optimize this version (e.g. removing the recursive call and making the function iterative so as not to be dependant upon the stack).



Method 2: Extended Euclidean Algorithm (using a chart)
This method is visually easier to understand, and it also runs faster than the method you posted (approximately 25% faster).

This method stems from the Euclidean Algorith, but goes about a more "visual" approach by using a chart.

Say we are looking for GDC(a,b) = d. We can initialize the chart as such:

Code:

a * x  +  b * y  =  r   q
---------------------------
    1  |     0   |  a | -
    0  |     1   |  b | -

Once the table has been initialized, each row of the table can be calculated via the following algorithm.

Code:

q = floor(r    / r   )
 n         n-2    n-1

floor doesn't necessarily need to be called in C++, as integer divisions automatically floor the result.

Then, each element of the row can be calculated like so:

Code:

element  = element    - q  * element
       n          n-2    n          n-1

So, to put this in an example, gdc(106,4):

Code:

106 * x  +  4 * y  =  r   q
---------------------------
      1  |      0  | 106| -
      0  |      1  |  4 | -
      1  |     -26 |  2 | 26
     -1  |      53 |  0 | 2

The gdc is the r(n-1) when r(n) = 0.

Hopefully that helped.

HomeworK??? No this is not homework. I have programmed in C for more than 15 years now. And about the tabs I was wondering if a tab length can be set here on this forum.. not in my Metrowerks CodeWarrior environment.

Thank you very much jverkoey for the quick reply! Could you please list your gcd( ) function here also so I can test and compare it with the one I posted? That would be really nice! I will run for-loops to test billions of combinations, rather than just one pair of numbers, to give accurate timings for a lot of cases.

> And about the tabs I was wondering if a tab length can be set here on this forum.
No - set your IDE to replace tabs with appropriate numbers of spaces before you post the code.

Pretty much every board / brower / IDE combination you can imagine is going to treat tabs differently, so the only real way to make sure your code looks the same to all is to indent it with spaces.

OK! Well, I would hate to use code that has tabs replaced with spaces, for obvious reasons. Code that has tabs replaced by spaces is not edit-friendly. I am very picky about how I format code. So even if it looks bad here with 8 space tabs, I prefer it over 4 spaces instead of a tab, since otherwise I will have to go all over the place fixing the tabs. Not a big deal if the code is worth it, but anyway!

By the way, here is another gcd( ) algorithm, small and elegant if the hardware has support for the % operator.. but it is about 50% slower than the longer gcd( ) I posted first.

Code:

int		GCD( int a, int b ) {
	int		r;
	
	while ( b ) {
		r = a % b;
		a = b;
		b = r;
	}
	
	return a;
}

Originally Posted by fischerandom

OK! Well, I would hate to use code that has tabs replaced with spaces, for obvious reasons. Code that has tabs replaced by spaces is not edit-friendly. I am very picky about how I format code.

It's not like it's hard to replace spaces with tabs.

Originally Posted by Rashakil Fol

It's not like it's hard to replace spaces with tabs.

Yes it is easy to replace each occurence of 4 spaces, etc, with a tab. But it will miss 3-space tabs, etc, that was ment to be a tab. Anyway, lets end this talk about tabs now ok! The subject is the GCD algorithm.
I am still waiting for jverkoeys reply to my question if he could post his 50% faster gcd( ) function.

Here you go:

Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define DEFAULT_NSPACES 4

int main(int argc, char **argv)
{
  int nspaces = DEFAULT_NSPACES;
  char buf[BUFSIZ], *p, *q;
  int i;

  if(argc > 2)
  {
    fputs("Usage: tabstospaces [<spaces per tab>]\n", stderr);
    exit(EXIT_FAILURE);
  }

  if(argc == 2)
  {
    nspaces = strtol(argv[1], &p, 0);
    if(nspaces < 0 || *p || !*argv[1])
    {
      fprintf(stderr,
        "Specified number of spaces is invalid: %s\n", argv[1]);
      exit(EXIT_FAILURE);
    }
  }

  while(fgets(buf, sizeof(buf), stdin))
  {
    p = buf;
    while((q = strchr(p, '\t')))
    {
      while(p < q)
      {
        fputc(*p, stdout);
        p++;
      }

      for(i = 0;i < nspaces;++i)
        fputc(' ', stdout);
      p++;
    }

    fputs(p, stdout);
  }

  return EXIT_SUCCESS;
}

Just use it like: tabstospaces [spaces per tab] < input_file > output_file

The spaces per tab is optional.

I'm sorry, I need to fix what I stated earlier. In the general case with completely random integers selected (50,000,000 benchmark) yours ran approximately 25-50% faster than the two algorithms I posted.

Sorry for any confusion, that's my fault on not doing a proper benchmark.

Originally Posted by itsme86

Here you go:

Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define DEFAULT_NSPACES 4

int main(int argc, char **argv)
{
  int nspaces = DEFAULT_NSPACES;
  char buf[BUFSIZ], *p, *q;
  int i;

  if(argc > 2)
  {
    fputs("Usage: tabstospaces [<spaces per tab>]\n", stderr);
    exit(EXIT_FAILURE);
  }

  if(argc == 2)
  {
    nspaces = strtol(argv[1], &p, 0);
    if(nspaces < 0 || *p || !*argv[1])
    {
      fprintf(stderr,
        "Specified number of spaces is invalid: %s\n", argv[1]);
      exit(EXIT_FAILURE);
    }
  }

  while(fgets(buf, sizeof(buf), stdin))
  {
    p = buf;
    while((q = strchr(p, '\t')))
    {
      while(p < q)
      {
        fputc(*p, stdout);
        p++;
      }

      for(i = 0;i < nspaces;++i)
        fputc(' ', stdout);
      p++;
    }

    fputs(p, stdout);
  }

  return EXIT_SUCCESS;
}

Just use it like: tabstospaces [spaces per tab] < input_file > output_file

The spaces per tab is optional.

What's this? I use Find and Replace in the IDE, and it works.

OK jverkoey, thank you for giving it a try! I am now back in my home in Stockholm where I have the book The Art of Computer Programming Volume 2 Seminumerical Algorithms Third Edition by Donald E. Knuth where the Greatest Common Divisor algorithm is discussed in very deep detail so now I have the information I need.
But if anyone finds a GCD algorithm that executes faster than the one I originally posted at the top, then please post it here!

Make up your mind! You just said it wasn't "edit friendly", now you're saying you already have a better solution? I think you just like to whine. Want some cheese with that?


Quzah.

Originally Posted by quzah

Make up your mind! You just said it wasn't "edit friendly", now you're saying you already have a better solution? I think you just like to whine. Want some cheese with that?


Quzah.

Using the IDE's Find and Replace does exactly the same job that itsme86 tried to acheive with his program, but is obviously much more efficient to use. However, what I mean is that if someone uses spaces instead of tabs to indent, the probability for being inconsistent, i.e., using 3 spaces here and 4 spaces there, is higher. After having dealt with hundreds of thousands of code lines I know this all too well. And I am very picky even with quite nicely indented code, such as Darwins kernel code. Examining it I just had to "fix" it the way I want it to look in just about every source file. That was before I knew about the program Indent, but I think its only for Windows and I am a Mac user. Haven't taken my time to write my own Indent app yet.