algorithm - what is the fastest way to find the gcd of n numbers?

Question

what is the fastest way to compute the greatest common divisor of n numbers?

Answer 1

Without recursion:

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

For very large arrays, it might be faster to use the fork-join pattern, where you split your array and calculate gcds in parallel. Here is some pseudocode:

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