algorithm - 找到 n 个数字的 gcd 的最快方法是什么？

Question

计算 n 个数的最大公约数的最快方法是什么？

Answer 1

没有递归:

int result = numbers[0];
for(int i = 1; i < numbers.length; i++){
    result = gcd(result, numbers[i]);
}
return result;

对于非常大的数组，使用 fork-join 模式可能会更快，您可以在其中拆分数组并并行计算 gcds。这是一些伪代码:

int calculateGCD(int[] numbers){
    if(numbers.length <= 2){
        return gcd(numbers);    
    }
    else {
        INVOKE-IN-PARALLEL {
            left = calculateGCD(extractLeftHalf(numbers));
            right = calculateGCD(extractRightHalf(numbers));
        }
        return gcd(left,right);
    }
}