Fast Greatest Common Divisor (GCD) Algorithm
The computational efficiency of the Euclid's algorithm is much higher that the alternatives
I would not recommend the Alternate 2 method for the following reasons:
1. First and foremost, the computational efficiency of the Euclid's algorithm at the core of my solution (see the following - ORIGINAL, RECOMMENDED) is significantly higher than of that simple iterations (essentially looping from the smaller half downward and checking divisibility of both variables) implemented in proposed alternative 1 (see the following):
// fast Euclid GCD algorithm for 2 integers: RECOMMENDED if (list.Length == 2) { Int64 a = list[0]; Int64 b = list[1]; while (b != 0) { GCD = b; b = a % b; a = GCD; } return GCD;
FYI: As per general theory, Euclidean algorithm should not take more steps to complete than 5 times the number of digits (base10) of the smallest number. Even more efficient algorithms than this classic, Euclidean one exist, but they are correspondingly, much more complex.
Note: FOLLOWING ALGORITHM (RE: Alternate 2) IS NOT RECOMMENDED DUE TO LOW EFFICIENCY
//Find the larger of the two numbers, the GCD can not be more than half of the smaller number. max = value1 > value2 ? (value2 / 2) : (value1 / 2); counter = max + 1; while ((!gcdFound) && (counter > 1)) { counter--; gcdFound = ((value1 % counter) == 0) && ((value2 % counter) == 0); }
2. Passing array and corresponding array operations, implemented in my original algorithm, are essential for extending it to more than just two input variables. There is no need to re-write my function, because it could be simply overloaded for just 2 variables (just add the second function, taking 2 parameters and calling the original one), or the same result could be achieved by simply passing the 2 variables value1 and value2 like in example shown below:
Int64 _gcd = GCD(new Int64[] {value1, value2 });
Hope I've answered the question.
Kind Regards,
Alexander Bell