34
$\begingroup$

I know that Euclid’s algorithm is the best algorithm for getting the GCD (great common divisor) of a list of positive integers. But in practice you can code this algorithm in various ways. (In my case, I decided to use Java, but C/C++ may be another option).

I need to use the most efficient code possible in my program.

In 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 in iterative mode, it looks like this:

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

There is also the Binary algorithm for the GCD, which may be coded simply like this:

int gcd (int a, int b)
{
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}
$\endgroup$
11
  • 5
    $\begingroup$ 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. $\endgroup$
    – Juho
    Commented Apr 22, 2012 at 18:35
  • 6
    $\begingroup$ 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. $\endgroup$
    – pad
    Commented Apr 22, 2012 at 19:15
  • 7
    $\begingroup$ 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. $\endgroup$
    – Louis
    Commented Apr 22, 2012 at 19:25
  • 2
    $\begingroup$ 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? $\endgroup$ Commented Nov 15, 2012 at 12:34
  • 4
    $\begingroup$ Note that there are asymptotically faster GCD algorithms. E.g. en.wikipedia.org/wiki/Binary_GCD_algorithm $\endgroup$
    – Neal Young
    Commented Nov 21, 2012 at 17:12

8 Answers 8

26
$\begingroup$

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).

$\endgroup$
0
9
$\begingroup$

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.

$\endgroup$
2
3
$\begingroup$

As I know Java doesn’t support tail recursion optimization in general, but you can test your Java implementation for it; if it doesn’t support it, a simple for-loop should be faster, otherwise recursion should be just as fast. On the other hand, these are bit optimizations, choose the code you think is easier and more readable.

I should also note that the fastest GCD algorithm is not Euclid’s algorithm, Lehmer’s algorithm is a bit faster.

$\endgroup$
1
  • $\begingroup$ Do you mean as far as I know? Do you mean the language specification does not mandate this optimisation (it would be surprising if it did), or that most implementations do not implement it? $\endgroup$
    – PJTraill
    Commented May 25, 2018 at 21:59
2
$\begingroup$

First, don't use recursivity to replace a tight loop. It is slow. Don't rely on the compiler to optimize it out. Second, 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.

$\endgroup$
2
  • 3
    $\begingroup$ “Avoid recursivity. It is slow” — presented as general advice, this is bogus. It depends on the compiler. Usually, even with compilers that don't optimize recursion, it isn't slow, just stack-consuming. $\endgroup$ Commented Jun 2, 2015 at 20:48
  • 4
    $\begingroup$ But for short code like this, the difference is significant. Stack-consuming means writing to and reading from memory. That is slow. The code above runs on 2 registers. Recursivity also means doing calls, which is longer than a conditional jump. A recursive call is much harder for branch prediction and harder to inline. $\endgroup$
    – Florian F
    Commented Jun 2, 2015 at 21:28
0
$\begingroup$

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++)

$\endgroup$
7
  • $\begingroup$ It doesn't look right. For b==1, it should return 1. And GCD[2,1000000000] will be slow. $\endgroup$
    – Florian F
    Commented Aug 31, 2014 at 20:55
  • 1
    $\begingroup$ Ah, yes, I made a mistake. Fixed (I think), and clarified. $\endgroup$ Commented Aug 31, 2014 at 20:58
  • $\begingroup$ Normally, GCD[a,0] should also return a. Yours loops forever. $\endgroup$
    – Florian F
    Commented Aug 31, 2014 at 21:19
  • 1
    $\begingroup$ I think the idea that modulo is slower than subtraction can be considered folklore. It holds both for small integers (subtraction usually takes one cycle, modulo rarely does) and for large integers (subtraction is linear, I'm not sure what the best complexity is for modulo but it's definitely worse than that). Of course you also need to consider the number of necessary iterations. $\endgroup$ Commented Jun 2, 2015 at 20:46
  • 1
    $\begingroup$ Even though this post does not directly answer the question, it brings up some valid points. Firstly it presents a third, valid GCD variant, which was not considered by the author of the question. While it is true that integer division has become much faster on modern CPUs, subtraction still is magnitudes faster in my experience. The author also carefully qualified his answer with "perhaps" and "for small numbers". I disagree with the criticism against this answer. $\endgroup$
    – DirkT
    Commented Sep 26, 2023 at 8:24
0
$\begingroup$

Disclaimer: Practical performance questions are highly application-specific and can only be satisfyingly answered by application-specific benchmarks that sufficiently represent field conditions. This answer uses a synthetic benchmark instead, which may not at all be representative of Your specific application.

A while ago, I ran a little synthetic benchmark (long version here) to answer, once and for all, which one of the following GCD algorithms is the fastest:

  • a) Subtraction-based Euclid's Algorithm
  • b) Division/Modulo-based Euclidean Algorithm
  • c) Binary GCD

The answer was a clear and resounding: d) A combination of all of the above. So without further ado, I proudly present to You: The tribrid GCD algorithm!

public static long tribridGCD( long x, long y )
{
  x = abs(x);
  y = abs(y);
  int l = Long.numberOfTrailingZeros(x); x >>>= l;
  int r = Long.numberOfTrailingZeros(y); y >>>= r;
  int shift = min(l,r);
  if( x > y ) {
    long z = x; x = y; y = z;
  }
  while( x != 0 ) {
    long z = x > (y>>>1) ? y-x : y%x;
    y = x;
    x = z;
    // Invariant: x <= y && (y is odd)
    x >>>= Long.numberOfTrailingZeros(x);
  }
  return y << shift;
}
$\endgroup$
0
$\begingroup$

What you present as the Binary GCD algorithm is not the Binary GCD algorithm, because it still uses the modulo (remainder) operator $\%$ (in fact it is the standard algorithm with the swap-via-xor trick, which probably makes it slower). This is unfair in the comparison as modulo is a costly operation. The real Binary algorithm only uses shifts and subtractions, notoriously fast.

Anyway, telling the most efficient algorithm is not possible for several reasons:

  • the answer can be machine-dependent,

  • the answer can even be dependent on the input value, and

  • the GCD is pretty fast to compute, and in practice it is impossible to measure short execution times accurately.

$\endgroup$
-2
$\begingroup$

Euclid Algorithm is most efficient for calculating GCD:

Static long gcd(long a,long b)
{
if(b==0)
return a;
else
return gcd(,a%b);
}

example:-

Let A = 16, B = 10.
GCD(16, 10) = GCD(10, 16 % 10) = GCD(10, 6)
GCD(10, 6) = GCD(6, 10 % 6) = GCD(6, 4)
GCD(6, 4) = GCD(4, 6 % 4) = GCD(4, 2)
GCD(4, 2) = GCD(2, 4 % 2) = GCD(2, 0)


Since B = 0 so GCD(2, 0) will return 2. 
$\endgroup$
1
  • 5
    $\begingroup$ This doesn't answer the question. The asker presents two versions of Euclid and asks which is faster. You don't seem to have noticed that and just declare the recursive version to be the only Euclid's algorithm, and assert with no evidence whatsoever that it's faster than everything else. $\endgroup$ Commented Oct 15, 2016 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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