3つ以上の数値のユークリッド最大公約数

Question

3つ以上の数値の最大公約数アルゴリズムを見つけるための例を挙げることができますか？

プログラミング言語は問題ではないと思います。

Answer 1

最初のペアから始めてGCDを取得し、その結果のGCDと次の番号を取得します。明らかな最適化は、実行中のGCDが1に達した場合に停止できることです。他の最適化があるかどうかを確認するためにこれを監視しています。 ：）

ああ、操作は可換/連想なので、これは簡単に並列化できます。

Answer 2

3つの数値のGCDは、 gcd（a、b、c）= gcd（gcd（a、b）、c）として計算できます。ユークリッドアルゴリズム、拡張ユークリッドアルゴリズム、またはバイナリGCDアルゴリズムを繰り返し適用して、答えを得ることができます。残念ながら、GCDを見つける他の（賢い？）方法を知りません。

Answer 3

私が知っているパーティーに少し遅れましたが、Sam Harwellのアルゴリズムの説明を利用した単純なJavaScriptの実装：

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

Answer 4

Javaの場合（最適ではありません）：

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;
}

Answer 5

このWikiページを更新しました。

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

これは、任意の数の用語を取ります。 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;
};

Answer 6

golangの場合、剰余を使用

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
}