Euclidean greatest common divisor for more than two numbers

Question

Can someone give an example for finding greatest common divisor algorithm for more than two numbers?

I believe programming language doesn't matter.

Illiquid

Answer 1

Start with the first pair and get their GCD, then take the GCD of that result and the next number. The obvious optimization is you can stop if the running GCD ever reaches 1. I'm watching this one to see if there are any other optimizations. :)

Oh, and this can be easily parallelized since the operations are commutative/associative.

Masbate

Answer 2

The GCD of 3 numbers can be computed as gcd(a, b, c) = gcd(gcd(a, b), c). You can apply the Euclidean algorithm, the extended Euclidian or the binary GCD algorithm iteratively and get your answer. I'm not aware of any other (more efficient) ways to find a GCD, unfortunately.

Overture

Answer 3

A little late to the party I know, but a simple JavaScript implementation, utilising Sam Harwell's description of the algorithm:

function euclideanAlgorithm(a, b) {
    if(b === 0) {
        return a;
    }
    const remainder = a % b;
    return euclideanAlgorithm(b, remainder)
}

function gcdMultipleNumbers(...args) { //ES6 used here, change as appropriate
  const gcd = args.reduce((memo, next) => {
      return euclideanAlgorithm(memo, next)}
  );

  return gcd;
}

gcdMultipleNumbers(48,16,24,96) //8

Elodea

Answer 4

I just updated a Wiki page on this.

[https://en.wikipedia.org/wiki/Binary_GCD_algorithm#C.2B.2B_template_class]

This takes an arbitrary number of terms. use GCD(5, 2, 30, 25, 90, 12);

template<typename AType> AType GCD(int nargs, ...)
{
    va_list arglist;
    va_start(arglist, nargs);

    AType *terms = new AType[nargs];

    // put values into an array
    for (int i = 0; i < nargs; i++) 
    {
        terms[i] = va_arg(arglist, AType);
        if (terms[i] < 0)
        {
            va_end(arglist);
            return (AType)0;
        }
    }
    va_end(arglist);

    int shift = 0;
    int numEven = 0;
    int numOdd = 0;
    int smallindex = -1;

    do
    {
        numEven = 0;
        numOdd = 0;
        smallindex = -1;

        // count number of even and odd
        for (int i = 0; i < nargs; i++)
        {
            if (terms[i] == 0)
                continue;

            if (terms[i] & 1)
                numOdd++;
            else
                numEven++;

            if ((smallindex < 0) || terms[i] < terms[smallindex])
            {
                smallindex = i;
            }
        }

        // check for exit
        if (numEven + numOdd == 1)
            continue;

        // If everything in S is even, divide everything in S by 2, and then multiply the final answer by 2 at the end.
        if (numOdd == 0)
        {
            shift++;
            for (int i = 0; i < nargs; i++)
            {
                if (terms[i] == 0)
                    continue;

                terms[i] >>= 1;
            }
        }

        // If some numbers in S  are even and some are odd, divide all the even numbers by 2.
        if (numEven > 0 && numOdd > 0)
        {
            for (int i = 0; i < nargs; i++)
            {
                if (terms[i] == 0)
                    continue;

                if ((terms[i] & 1)  == 0) 
                    terms[i] >>= 1;
            }
        }

        //If every number in S is odd, then choose an arbitrary element of S and call it k.
        //Replace every other element, say n, with | n−k | / 2.
        if (numEven == 0)
        {
            for (int i = 0; i < nargs; i++)
            {
                if (i == smallindex || terms[i] == 0)
                    continue;

                terms[i] = abs(terms[i] - terms[smallindex]) >> 1;
            }
        }

    } while (numEven + numOdd > 1);

    // only one remaining element multiply the final answer by 2s at the end.
    for (int i = 0; i < nargs; i++)
    {
        if (terms[i] == 0)
            continue;

        return terms[i] << shift;
    }
    return 0;
};

Octo

Answer 5

For golang, using remainder

func GetGCD(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}
func GetGCDFromList(numbers []int) int {
    var gdc = numbers[0]
    for i := 1; i < len(numbers); i++ {
        number := numbers[i]
        gdc  = GetGCD(gdc, number)
    }
    return gdc
}

Deviltry

Answer 6

In Java (not optimal):

public static int GCD(int[] a){
    int j = 0;

    boolean b=true;
    for (int i = 1; i < a.length; i++) {
        if(a[i]!=a[i-1]){
            b=false;
            break;
        }
    }
    if(b)return a[0];
    j=LeastNonZero(a);
    System.out.println(j);
    for (int i = 0; i < a.length; i++) {
        if(a[i]!=j)a[i]=a[i]-j;
    }
    System.out.println(Arrays.toString(a));
    return GCD(a);
}

public static int LeastNonZero(int[] a){
    int b = 0;
    for (int i : a) {
        if(i!=0){
            if(b==0||i<b)b=i;
        }
    }
    return b;
}

Bacitracin

While the answer is correct and it's nice of you to supply an answer for an unanswered question, explaining your answer would make it a great one. It's important for the OP to not only receive the correct answer but also to understand it! – Tetreault

@Tetreault What do you mean by an unanswered question? Was this originally part of a different question that was (duplicate) merged into this one? I do agree that this answer needs to have more of an explanation. – Outsell

Oh sorry, I found this answer in the review queue and assumed it was unanswered because of your first sentence. My mistake, the other answers didn't show there. -- BTW the review queue is a list of questions that are to be peer evaluated such as first time answers (like yours) or posts that need editing. – Tetreault

Answer 7

Euclid's algorithm can be extended to work on multiple inputs.
In python, easy to understand:

def gcd(vals : list[int]):
    while len(vals) > 1:
        m = min(vals)
        vals = list(x % m for x in vals if x % m) + [m]
    return vals[0]

Or in C++, operating in place, without using the global minimum value:

template<typename T>
T gcd(T *vals, size_t sz)
{
  T& minval = vals[0];

  while (sz > 1 && minval > 1)
  {
    // next size
    size_t j = 1;

    for (size_t i=1; i < sz; i++)
    {

      // Track the minimum value
      if (minval > vals[i])
      {
        std::swap(minval, vals[i]);
        if (minval == 1)
          break; // early exit
      }

      // Keep only the non-zero reminders
      if ((vals[i] % minval) > 0)
        vals[j++] = vals[i] % minval;
    }

    sz = j;
  }

  return minval;
}

For small number of values it should be faster to find the global minimum in a separate pass.

Judi