Menu
what is the fastest way to compute the greatest common divisor of n numbers?
599
Step 1: Applying Euclid's division lemma to a and b we get two whole numbers q and r such that, a = bq+r ; 0 r < b. Step 2: If r = 0, then b is the HCF of a and b. If r ≠0, then apply Euclid's division lemma to b and r. Step 3: Continue the above process until the remainder is zero.
Algorithm to find GCD using Stein's algorithm gcd(a, b) gcd(a, 0) = a and gcd(0, b) = b because everything divides 0. If a and b are both even, gcd(a, b) = 2*gcd(a/2, b/2) because 2 is a common divisor. Multiplication with 2 can be done with bitwise shift operator. gcd(a, b) = gcd(a, b/2).
In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder.
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); } } If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
