11,478,174 members (69,680 online)
Alternative Tip/Trick

# Fast Greatest Common Divisor (GCD) Algorithm

, 15 Feb 2011 CPOL 8.9K 2
 Rate this:
Hi, everybodyAfter thorough consideration, 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 function(see the following - ORIGINAL, RECOMMENDED): // fast Euclid...
Hi, everybody

After thorough consideration, 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 function(see the following - ORIGINAL, RECOMMENDED):
```          // 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;```

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

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);
}```

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.

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#, HTML5, jQuery, SQL, 'Big Data', AI, Speech Tech and Mobile apps. He participated in App Innovation Contest (AIC 2102/2013) with several winning submissions. Sample projects/pubs follow:

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