Thread: GCD as fast as possible!

  1. #1
    Registered User fischerandom's Avatar
    Join Date
    Aug 2005
    Location
    Stockholm
    Posts
    71

    Cool 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!!

  2. #2
    ... kermit's Avatar
    Join Date
    Jan 2003
    Posts
    1,534
    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.

  3. #3
    Software Developer jverkoey's Avatar
    Join Date
    Feb 2003
    Location
    New York
    Posts
    1,905
    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.

  4. #4
    Registered User fischerandom's Avatar
    Join Date
    Aug 2005
    Location
    Stockholm
    Posts
    71
    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.

  5. #5
    Registered User fischerandom's Avatar
    Join Date
    Aug 2005
    Location
    Stockholm
    Posts
    71
    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.

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > 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.

  7. #7
    Registered User fischerandom's Avatar
    Join Date
    Aug 2005
    Location
    Stockholm
    Posts
    71
    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;
    }

  8. #8
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote 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.

  9. #9
    Registered User fischerandom's Avatar
    Join Date
    Aug 2005
    Location
    Stockholm
    Posts
    71
    Quote 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.

  10. #10
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    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.
    Last edited by itsme86; 11-21-2005 at 10:56 AM.
    If you understand what you're doing, you're not learning anything.

  11. #11
    Software Developer jverkoey's Avatar
    Join Date
    Feb 2003
    Location
    New York
    Posts
    1,905
    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.
    Last edited by jverkoey; 11-21-2005 at 01:57 PM.

  12. #12
    Registered User fischerandom's Avatar
    Join Date
    Aug 2005
    Location
    Stockholm
    Posts
    71
    Quote 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.
    Last edited by fischerandom; 11-21-2005 at 04:47 PM.

  13. #13
    Registered User fischerandom's Avatar
    Join Date
    Aug 2005
    Location
    Stockholm
    Posts
    71
    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!

  14. #14
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  15. #15
    Registered User fischerandom's Avatar
    Join Date
    Aug 2005
    Location
    Stockholm
    Posts
    71
    Quote 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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Gcd on three numbers
    By Ideswa in forum C Programming
    Replies: 7
    Last Post: 03-19-2009, 01:57 PM
  2. Saving a part of screen into a file fast!
    By Zap in forum C++ Programming
    Replies: 4
    Last Post: 06-28-2003, 10:56 AM
  3. Super fast bilinear interpolation
    By VirtualAce in forum Game Programming
    Replies: 2
    Last Post: 06-18-2002, 09:35 PM
  4. moving a bitmap, fast and smooth
    By werdy666 in forum Game Programming
    Replies: 1
    Last Post: 05-31-2002, 06:49 PM
  5. GCD For all of You!
    By Argentina in forum C Programming
    Replies: 0
    Last Post: 02-14-2002, 04:38 PM