Welcome, guest | Sign In | My Account | Store | Cart

GCD of an arbitrary list (Python recipe) by Jason Schorn
ActiveState Code (http://code.activestate.com/recipes/577512/)

Given an arbitrary list (of length >= 1) of positive integers, return the greatest common divisor (gcd) of the list.

Python, 23 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/usr/bin/python

def gcd(*args):
    if len(args) == 1:
        return args[0]

    L = list(args)

    while len(L) > 1:
        a = L[len(L) - 2]
        b = L[len(L) - 1]
        L = L[:len(L) - 2]
        
        while a:
            a, b = b%a, a

        L.append(b)
        
    return abs(b)

#if __name__ == "__main__":

print gcd(68, 14, 9, 36, 126)

We utilize the fact the gcd is associative, i.e. gcd(a, b, c) = gcd(gcd(a, b), c) = gcd(a, gcd(b, c)), in order to compute the gcd of an arbitrary list of positive integers. You should note that we do NOT check user input for such things as: gcd(-3, 9) or gcd(3.14159, 2.71828). Further, the desired end result could be completed as follows:

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

and

def gcd(*args):
    return reduce(g, args)

using less code but the ideas was to build a single function that computes the gcd of some list of integers. Enjoy and let me know if you find a more succinct way.

Tags: arbitrary, common, divisor, gcd, greatest, list, schorn