I know that Euclid'sEuclid’s algorithm is the best algorithm for getgetting the GCD (great common divisor) forof a list theof positive integer numbersintegers. But, in the practice, you can write two codes por evaluate the gcdcode this algorithm in various ways. (forIn my case, iI decided to use javaJava, but cC/c++C++ may be another option).
I need to getuse the most efficient code of two possibilities form to programmingpossible in my program.
Recursive ModeIn 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;
}
We can do that withThere is also the Binary algorithm for the GCD, and the easy code iswhich may be coded simply like thatthis:
int gcd (int a, int b)
{
while(b) b ^= a ^= b ^= a %= b;
return a;
}