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

Themasterhimself picture Themasterhimself · Feb 3, 2011 · Viewed 60.6k times · Source

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

Answer

dogbane picture dogbane · Feb 3, 2011

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