12,451,662 members (58,543 online)
Alternative Tip/Trick
alternative version

12.8K views
2 bookmarked
Posted

# Fast Greatest Common Divisor (GCD) Algorithm

, 15 Feb 2011 CPOL
 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 is a full-stack software developer (Win/Web/Mobile). He holds PhD in EE/IT, published 300+ articles, authored 37 inventions and is credited for 10+ Enterprise level projects; currently focused on HTML5/CSS3, Javascript/jQuery, .NET/WPF/C#, Android/Angular.js, 'Big Data', AI, IoT. Alex participated in App Innovation Contests (AIC 2102/2013) with multiple winning submissions. Sample projects/pubs:

## You may also be interested in...

 Pro Pro

 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
 Reason for my vote of 5 Deserves a 5 for detailed explanation!
 Last Visit: 31-Dec-99 18:00     Last Update: 28-Aug-16 3:05 Refresh 1