65.9K
CodeProject is changing. Read more.
Home

Fast Greatest Common Divisor (GCD) Algorithm

starIconstarIconstarIconstarIconstarIcon

5.00/5 (2 votes)

Feb 12, 2011

CPOL

1 min read

viewsIcon

24111

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