pythonmathgreatest-common-divisor

Euclidean algorithm (GCD) with multiple numbers?


So I'm writing a program in Python to get the GCD of any amount of numbers.

def GCD(numbers):

    if numbers[-1] == 0:
        return numbers[0]


    # i'm stuck here, this is wrong
    for i in range(len(numbers)-1):
        print GCD([numbers[i+1], numbers[i] % numbers[i+1]])


print GCD(30, 40, 36)

The function takes a list of numbers. This should print 2. However, I don't understand how to use the the algorithm recursively so it can handle multiple numbers. Can someone explain?

updated, still not working:

def GCD(numbers):

    if numbers[-1] == 0:
        return numbers[0]

    gcd = 0

    for i in range(len(numbers)):
        gcd = GCD([numbers[i+1], numbers[i] % numbers[i+1]])
        gcdtemp = GCD([gcd, numbers[i+2]])
        gcd = gcdtemp

    return gcd

Ok, solved it

def GCD(a, b):

    if b == 0:
        return a
    else:
        return GCD(b, a % b)

and then use reduce, like

reduce(GCD, (30, 40, 36))

Solution

  • Since GCD is associative, GCD(a,b,c,d) is the same as GCD(GCD(GCD(a,b),c),d). In this case, Python's reduce function would be a good candidate for reducing the cases for which len(numbers) > 2 to a simple 2-number comparison. The code would look something like this:

    if len(numbers) > 2:
        return reduce(lambda x,y: GCD([x,y]), numbers)
    

    Reduce applies the given function to each element in the list, so that something like

    gcd = reduce(lambda x,y:GCD([x,y]),[a,b,c,d])
    

    is the same as doing

    gcd = GCD(a,b)
    gcd = GCD(gcd,c)
    gcd = GCD(gcd,d)
    

    Now the only thing left is to code for when len(numbers) <= 2. Passing only two arguments to GCD in reduce ensures that your function recurses at most once (since len(numbers) > 2 only in the original call), which has the additional benefit of never overflowing the stack.