11,712,241 members (77,310 online)
Alternative Tip/Trick

# Fast Greatest Common Divisor (GCD) Algorithm

, 15 Feb 2011 CPOL 9.9K 2
 Rate this:
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 });

Kind Regards,
Alexander Bell

## Share

 President Infosoft International Inc United States
Dr. A. Bell has 20+ years of Software and Electrical Engineering experience: Win/Web veteran, published 300+ articles and authored 37 inventions, credited for 10+ Enterprise level projects (>250k code lines); currently focused on .NET/WPF/C#, Javascript/jQuery, 'Big Data', AI, IoT and Mobile apps. Participated in App Innovation Contest (AIC 2102/2013) with several winning submissions. Sample projects/pubs follow:

## You may also be interested in...

 First Prev Next
 Thanks, Sandeep! Best regards/wishes, Alex DrABELL12-Feb-11 4:12 DrABELL 12-Feb-11 4:12
 Reason for my vote of 5 Deserves a 5 for detailed explanat... Sandeep Mewara11-Feb-11 20:58 Sandeep Mewara 11-Feb-11 20:58
 Last Visit: 31-Dec-99 18:00     Last Update: 1-Sep-15 7:30 Refresh 1