Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles
(untagged)

Fast Greatest Common Divisor (GCD) Algorithm

0.00/5 (No votes)
15 Feb 2011 1  
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

 

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here