Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I know that Euclid's algorithm is the best algorithm for get the GCD (great common divisor) for a list the positive integer numbers. But, in the practice, you can write two codes por evaluate the gcd (for my case, i decided use java, but c/c++ may be another option).

I need to get the most efficient code of two possibilities form to programming.

Recursive Mode, you can write...

static long gcd(long a, long b){
    a = Math.abs(a); b = Math.abs(b);
    return (b==0) ? a : gcd(b, a%b);
  }

And, iterative mode, looks like ...

static long gcd(long a, long b) {
  long r, i;
  while(b!=0){
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

We can do that with the Binary GCD, and the easy code is like that

int gcd(int a, int b)
{
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}
share|improve this question
2  
I think this is too subjective, and perhaps even better suited for StackOverflow. "Most efficient in practice" depends on many (even unpredictable) factors, such as the underlying architechture, memory hierarchy, size and form of the input etc. –  Juho Apr 22 '12 at 18:35
5  
This is the same algorithm expressed in recursive and iterative ways. I think their difference is negligible since Euclid algorithm converges pretty fast. Choose one that fits your preference. –  pad Apr 22 '12 at 19:15
5  
You might want to try profiling these two. Since the recursive version is a tail call, it is not unlikely that the compiler actually emits almost the same code. –  Louis Apr 22 '12 at 19:25
1  
this is wrong. should be while b != 0, and then return a. Otherwise it bugs out on division by zero. also don't use recursion if you have really big gcds....you get a pile of stack and function states...why not just go iterative? –  Cris Stringfellow Nov 15 '12 at 12:34
1  
Note that there are asymptotically faster GCD algorithms. E.g. en.wikipedia.org/wiki/Binary_GCD_algorithm –  Neal Young Nov 21 '12 at 17:12

5 Answers 5

up vote 3 down vote accepted

As I know java doesn't supports tail recursion optimization in general, but you can test it for your case, if it doesn't supports, simple for loop should be faster else they are same as each other, but these are bit optimization, choose the one you think is easier and more readable. I should note that fastest GCD algorithm is not euclidean algorithm, Lehmer's algorithm is a bit faster.

share|improve this answer

Your two algorithms are equivalent (at least for positive integers, what happens with negative integers in the imperative version depends on Java's semantics for % which I don't know by heart). In the recursive version, let $a_i$ and $b_i$ be the argument of the $i$th recursive call: $$\begin{gather*} a_{i+1} = b_i \\ b_{i+1} = a_i \mathbin{\mathrm{mod}} b_i \\ \end{gather*}$$

In the imperative version, let $a'_i$ and $b'_i$ be the values of the variables a and b at the beginning of the $i$th iteration of the loop. $$\begin{gather*} a'_{i+1} = b'_i \\ b'_{i+1} = a'_i \mathbin{\mathrm{mod}} b'_i \\ \end{gather*}$$

Notice a resemblance? Your imperative version and your recursive version are calculating exactly the same values. Furthermore, they both end at the same time, when $a_i=0$ (resp. $a'_i=0$), so they perform the same number of iterations. So algorithmically speaking, there is no difference between the two. Any difference will be a matter of implementation, highly dependent on the compiler, the hardware it runs on, and quite possibly the operating system and what other programs are running concurrently.

The recursive version makes only tail recursive calls. Most compilers for imperative languages do not optimize these, and so it is likely that the code they generate will waste a little time and memory constructing a stack frame at each iteration. With a compiler that optimizes tail calls (compilers for functional languages almost always do), the generated machine code may well be the same for both (assuming you harmonize those calls to abs).

share|improve this answer

For small numbers, % is quite an expensive operation, perhaps the simpler recursive

GCD[a,b] := Which[ 
   a==b , Return[a],
   b > a, Return[ GCD[a, b-a]],
   a > b, Return[ GCD[b, a-b]]
];

is quicker? (Sorry, Mathematica code and not C++)

share|improve this answer
    
It doesn't look right. For b==1, it should return 1. And GCD[2,1000000000] will be slow. –  Florian F Aug 31 at 20:55
    
Ah, yes, I made a mistake. Fixed (I think), and clarified. –  Per Alexandersson Aug 31 at 20:58
    
Normally, GCD[a,0] should also return a. Yours loops forever. –  Florian F Aug 31 at 21:19

First, avoid recursivity. It is slow. Don't rely on the compiler to optimize it out. By the way, in your code, you call Math.abs() within every recursive calls, which is useless.

In your loop, you can easily avoid temporary variables and swapping a and b all the time.

int gcd(int a, int b){
    if( a<0 ) a = -a;
    if( b<0 ) b = -b;
    while( b!=0 ){
        a %= b;
        if( a==0 ) return b;
        b %= a;
    }
    return a;
}

Swapping using the a ^= b ^= a ^= b makes the source shorter but takes many instructions to execute. It will be slower than the boring swap with a temporary variable.

share|improve this answer

For numbers that are small, the binary GCD algorithm is sufficient.

GMP, a well maintained and real-world tested library, will switch to a special half GCD algorithm after passing a special threshold, a generalization of Lehmer's Algorithm. Lehmer's uses matrix multiplication to improve upon the standard Euclidian algorithms. According to the docs, the asymptotic running time of both HGCD and GCD is O(M(N)*log(N)), where M(N) is the time for multiplying two N-limb numbers.

Full details on their algorithm can be found here.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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