Greatest common divisor algorithms OTHER than Euclid's

Question

I'm supposed to basically generate 3 different algorithms for finding the GCD (a,b).

One of them is the Euclid's version, so I need two more.

Implementation is done in C#.

Suggestions?

Answer 1

(Note that when computing gcd(a,b), we can assume that a <= b; if that were not true, we could just swap them.)

The Euclidean algorithm is certainly the most efficient way to compute the gcd. But if you need two other (inefficient) ways to compute gcd(a,b), there are plenty:

1. Starting from a and going down, test every number to see if it divides both a and b.

2. Prime-factorize a and b (obtaining multisets of primes), and return the product of the intersection of these multisets.

3. Find all divisors of a, and test if they divide b starting from a and going down.

4. Find lcm(a,b) by testing which of b, 2*b, 3*b, ... is divisible by a, and return a*b/(lcm(a,b)).

1 and 4 are probably easiest to implement, since they don't involve factoring.

It's also important to note some edge cases: gcd(0,x) = x for all x > 0, while gcd(0,0) is undefined. And technically I suppose gcd(a,b) = gcd(abs(a), abs(b)) covers the case where inputs may be negative.

Answer 2

These are the three most used algorithms:

public static uint FindGCDModulus(uint value1, uint value2)
{
while(value1 != 0 && value2 != 0)
{
        if (value1 > value2)
        {
                value1 %= value2;
        }
        else
        {
                value2 %= value1;
        }
}
return Math.Max(value1, value2);
   }

public static uint FindGCDEuclid(uint value1, uint value2)
  {
while(value1 != 0 && value2 != 0)
{
        if (value1 > value2)
        {
                value1 -= value2;
        }
        else
        {
                value2 -= value1;
        }
}
return Math.Max(value1, value2);
}

 public static uint FindGCDStein(uint value1, uint value2)
 {
if (value1 == 0) return value2;
if (value2 == 0) return value1;
if (value1 == value2) return value1;

bool value1IsEven = (value1 & 1u) == 0;
bool value2IsEven = (value2 & 1u) == 0;

if (value1IsEven && value2IsEven)
{
        return FindGCDStein(value1 >> 1, value2 >> 1) << 1;
}
else if (value1IsEven && !value2IsEven)
{
        return FindGCDStein(value1 >> 1, value2);
}
else if (value2IsEven)
{
        return FindGCDStein(value1, value2 >> 1);
}
else if (value1 > value2)
{
        return FindGCDStein((value1 - value2) >> 1, value2);
}
else
{
        return FindGCDStein(value1, (value2 - value1) >> 1);
}
}

Answer 3

This is one of the alternatives:

public static int gcd(int x, int y) {
    int result = 0;

    if (x<0) {
        x = -x;
    }
    if (y<0) {
        y = -y;
    }
    if (x == 0){
        result = y; 
    }
    if (y == 0){
        result = x; 
    }
    for (int i = 1; i < x+1; i++) {

        if ( x % i == 0) {

            if ( y % i == 0) {
                result = i;
            }
        }   
    } 
    return result; }

Answer 4

A more or less direct way is the following code, which is derived from Pick's theorem:

int gcd(int a, int b)
{

     if( a < 0)
     {
         a = -a;
     }

     if( b < 0)
     {
         b = -b;
     }

     if( a == b)
     {
          return a;
     }

     //swap the values to make the upper bound in the next loop minimal
     if( a > b)
     {
        int swap = a;
        a = b;
        b = swap;
     }
     

     int temp=0;

     for(int i=1; i<=a; i++)
     {
          temp += math.floor(b*i/a);
     }

     return (a*b + b - a + temp)/2;
}