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

15

44

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

Emmaline answered 3/2, 2011 at 11:26 Comment(6)
finding GCD recursively is the fastest known method. Do you want some kind of special optimization?Foster
@Gunner: The question is about the GCD of more than 2 arguments.Napier
@ Marcelo Cantos: The concept is still same.Foster
Every method I can think of that does not use the fact that gcd(a,b,c)=gcd(gcd(a,b),c) is slower.Slough
Why do you ask? Using gcd(a,b,c)=gcd(gcd(a,b),c) is the best method, much faster in general than using for example factorization. In fact, for polynomials one uses gcd with the derivative first to find factors which occurs more than once.Footrest
I'd probably try to find the greatest common power of base of number representation by counting common trailing zeros, followed by taking the remainder from dividing the second smallest number in set by the smallest - wait, this is just GCD from smallest to largest. Meh. Look for Lehmer and why matrix multiplication helps it.Lickspittle
T
3

You should use Lehmer's GCD algorithm.

Tripinnate answered 20/11, 2014 at 10:57 Comment(0)
L
20

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);
    }
}
Loathing answered 3/2, 2011 at 11:39 Comment(0)
D
18

You may want to sort the numbers first and compute the gcd recursively starting from the smallest two numbers.

Deliberate answered 3/2, 2011 at 14:56 Comment(0)
D
4

C++17

I have written this function for calculating gcd of n numbers by using C++'s inbuilt __gcd(int a, int b) function.

int gcd(vector<int> vec, int vsize)
{
    int gcd = vec[0];
    for (int i = 1; i < vsize; i++)
    {
        gcd = __gcd(gcd, vec[i]);
    }
    return gcd;
}

To know more about this function visit this link .

Also refer to Dijkstra's GCD algorithm from the following link. It works without division. So it could be slightly faster (Please correct me if I am wrong.)

Deform answered 13/7, 2016 at 7:57 Comment(1)
(The subtraction version is what seems to have been presented by Euclid - and it was old when he did. Speed compared to remainder versions should be machine dependant.)Lickspittle
T
3

You should use Lehmer's GCD algorithm.

Tripinnate answered 20/11, 2014 at 10:57 Comment(0)
B
2

How about the following using Euclidean algorithm by subtraction:

function getGCD(arr){
    let min = Math.min(...arr); 
    let max= Math.max(...arr);
    if(min==max){
        return min;
    }else{
         for(let i in arr){
            if(arr[i]>min){
                arr[i]=arr[i]-min;
            }
        }
        return getGCD(arr);
    }
   
}

console.log(getGCD([2,3,4,5,6]))

The above implementation takes O(n^2) time. There are improvements that can be implemented but I didn't get around trying these out for n numbers.

Brunella answered 2/4, 2019 at 14:48 Comment(0)
M
1

If you have a lot of small numbers, factorization may be actually faster.

//Java
int[] array = {60, 90, 45};
int gcd = 1;
outer: for (int d = 2; true; d += 1 + (d % 2)) {
    boolean any = false;
    do {
        boolean all = true;
        any = false;
        boolean ready = true;
        for (int i = 0; i < array.length; i++) {
            ready &= (array[i] == 1);
            if (array[i] % d == 0) {
                any = true;
                array[i] /= d;
            } else all = false;
        }
        if (all) gcd *= d;
        if (ready) break outer;
    } while (any);
}
System.out.println(gcd);

(works for some examples, but not really tested)

Mooncalf answered 4/2, 2011 at 14:46 Comment(0)
C
1

Use the Euclidean algorithm :

function gcd(a, b)
while b ≠ 0
   t := b; 
   b := a mod b; 
   a := t; 
return a;

You apply it for the first two numbers, then the result with the third number, etc... :

read(a);
read(b);

result := gcd(a, b);
i := 3;
while(i <= n){
    read(a)
    result := gcd(result, a);
}
print(result);
Colonnade answered 23/11, 2016 at 19:18 Comment(1)
And in the cycle if you get '1' for the result you can stop the cycleLegalize
P
1

Here below is the source code of the C program to find HCF of N numbers using Arrays.

#include<stdio.h>

int main()
{
    int n,i,gcd;
    printf("Enter how many no.s u want to find gcd : ");
    scanf("%d",&n);
    int arr[n];
    printf("\nEnter your numbers below :- \n ");
    for(i=0;i<n;i++)
    {
        printf("\nEnter your %d number = ",i+1);
        scanf("%d",&arr[i]);
    }
    gcd=arr[0];
    int j=1;
    while(j<n)
    {
       if(arr[j]%gcd==0)
       {
           j++;
       }
       else
       {
           gcd=arr[j]%gcd;
           i++;
       }
    }
    printf("\nGCD of k no.s = %d ",gcd);
    return 0;
}

For more refer to this website for further clarification.......

Progestational answered 6/3, 2017 at 18:22 Comment(1)
There's a typo in the while's else block, should be j++ instead of i++. Or even without this line. Be careful, with second j++ it won't work properly 100% of times. For example in the array [3166277268, 14314056372, 3166277268, 1241634933, 11582623668, 3353406672, 4050665157, 11002134528, 14642726637, 14183632848] with j++ it will return 7834365 without - 74613Novelette
V
1

You can use divide and conquer. To calculate gcdN([]), you divide the list into first half and second half. if it only has one num for each list. you calculate using gcd2(n1, n2).

I just wrote a quick sample code. (assuming all num in the list are positive Ints)

def gcdN(nums):
    n = len(nums)
    if n == 0: return "ERROR"
    if n == 1: return nums[0]
    if n >= 2: return gcd2(gcdN(nums[:n//2]), gcdN(nums[n//2:]))

def gcd2(n1, n2):
    for num in xrange(min(n1, n2), 0, -1):
        if n1 % num == 0 and n2 % num == 0:
            return num
Vadose answered 5/4, 2017 at 1:43 Comment(0)
R
0

Here's a gcd method that uses the property that gcd(a, b, c) = gcd(a, gcd(b, c)).
It uses BigInteger's gcd method since it is already optimized.

public static BigInteger gcd(BigInteger[] parts){
    BigInteger gcd = parts[0];
    for(int i = 1; i < parts.length; i++)
        gcd = parts[i].gcd(gcd);
    return gcd;
}
Realistic answered 9/5, 2016 at 21:12 Comment(0)
O
0
//Recursive solution to get the GCD of Two Numbers

long long int gcd(long long int a,long long int b)<br>
{
   return b==0 ? a : gcd(b,a%b);
}
int main(){
  long long int a,b;
  cin>>a>>b;
  if(a>b) cout<<gcd(a,b);
  else cout<<gcd(b,a);
return 0;
}
Ofilia answered 2/8, 2016 at 15:15 Comment(0)
H
0
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

class GCDArray{
    public static int [] extractLeftHalf(int [] numbers)
    {
        int l =numbers.length/2;
        int arr[] = Arrays.copyOf(numbers, l+1);
        return arr;
    }

    public static int [] extractRightHalf(int [] numbers)
    {
        int l =numbers.length/2;
        int arr[] = Arrays.copyOfRange(numbers,l+1, numbers.length);
        return arr;
    }

    public static int gcd(int[] numbers)
    {
        if(numbers.length==1)
            return numbers[0];
        else {
            int x = numbers[0];
            int y = numbers[1];
            while(y%x!=0)
            {
                int rem = y%x;
                y = x;
                x = rem;
            }
            return x;
        }
    }
    public static int gcd(int x,int y)
    {
            while(y%x!=0)
            {
                int rem = y%x;
                y = x;
                x = rem;
            }
            return x;

    }
    public static int calculateGCD(int[] numbers){
        if(numbers.length <= 2){
            return gcd(numbers);    
        }
        else {

                    int left = calculateGCD(extractLeftHalf(numbers));
                    int right = calculateGCD(extractRightHalf(numbers));

            return gcd(left,right);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        System.out.println(calculateGCD(arr));
    }
}

**

Above is the java working code ..... the pseudo code of which is already mention by https://stackoverflow.com/users/7412/dogbane

**

Heddie answered 18/1, 2017 at 14:25 Comment(3)
This is not adding any new information since the pseudocode is already their. Additionally this question is about a concept, not the practical implementation in any language.Vulpine
ya you are right ...but i think it will be helpful for someone... but thanks for you comment :)Heddie
I definitely see your good intention here, but having such an answer means that we would also have to take similar answers for all other possible languages. This would make it really hard to find any usefull information here.Vulpine
B
0

A recursive JavaScript (ES6) one-liner for any number of digits.

const gcd = (a, b, ...c) => b ? gcd(b, a % b, ...c) : c.length ? gcd(a, ...c) : Math.abs(a);
Boris answered 27/7, 2017 at 14:5 Comment(0)
S
0

This is what comes off the top of my head in Javascript.

function calculateGCD(arrSize, arr) {
    if(!arrSize)
        return 0;
    var n = Math.min(...arr);
    for (let i = n; i > 0; i--) {
        let j = 0;
        while(j < arrSize) {
            if(arr[j] % i === 0) {
                j++;
            }else {
                break;
            }
            if(j === arrSize) {
                return i;
            }
        }
    }
}

console.log(generalizedGCD(4, [2, 6, 4, 8]));
// Output => 2
Splutter answered 25/3, 2020 at 8:13 Comment(1)
Please add an assessment of the number of operations needed. Compare it to one of the pairwise GCD approaches of pre-existing answers.Lickspittle
E
-4

Here was the answer I was looking for. The best way to find the gcd of n numbers is indeed using recursion.ie gcd(a,b,c)=gcd(gcd(a,b),c). But I was getting timeouts in certain programs when I did this.

The optimization that was needed here was that the recursion should be solved using fast matrix multiplication algorithm.

Emmaline answered 3/6, 2011 at 13:51 Comment(2)
An accepted answer with two down votes? This is why, I have trust issues.Cruzeiro
There is a "half-GCD" algorithm used in GNU MultiPrecision, which purportedly uses matrix multiplication: Subquadratic GCD, based on Niels Möller, “On Schönhage’s algorithm and subquadratic integer GCD computation”, in Mathematics of Computation, volume 77, January 2008, pp. 589-607. (From just squinting my eyes, GMP does not seem to directly support GCD of more than two numbers.)Lickspittle

© 2022 - 2024 — McMap. All rights reserved.