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

Finding the GCD of a list of numbers (a.k.a. Reducing numbers in a list) (Python recipe) by Stephen Akiki
ActiveState Code (http://code.activestate.com/recipes/577282/)

http://akiscode.com/articles/gcd_of_a_list.shtml

This python code snippet allows you to find the GCD of a list of numbers, after this it is a simple matter of diving all the numbers in the list by the GCD to reduce it.

Why this works...

The GCD of a list of numbers [a, b, c] is GCD(GCD(a, b), c). The reduce function does exactly this and thus gives you the GCD of all the numbers in 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
# http://akiscode.com/articles/gcd_of_a_list.shtml
# Copyright (c) 2010 Stephen Akiki
# MIT License (Means you can do whatever you want with this)
#  See http://www.opensource.org/licenses/mit-license.php
# Error Codes:
#   None

def GCD(a,b):
	""" The Euclidean Algorithm """
	a = abs(a)
	b = abs(b)
        while a:
                a, b = b%a, a
        return b
        
        
def GCD_List(list):
	""" Finds the GCD of numbers in a list.
	Input: List of numbers you want to find the GCD of
		E.g. [8, 24, 12]
	Returns: GCD of all numbers
	"""
	return reduce(GCD, list)
Tags: common, denominator, gcd, greatest, lisst, reduce

1 comment

Jason Schorn 13 years, 4 months ago  # | flag

Just a couple of points to make:

  1. Why abs()? Either assume the person using the function knows to use positive integers or note that gcd(-6, 8) = (+-)2 are valid answers despite not adhering to the Euclidean algorithm. Alternatively, try return abs(b).

  2. Without coding for errors/awful user input try.

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


def GCD_List(*args):
    return reduce(GCD, args)

Note the following:

  1. The use of *args let you use the function as GCD_List(a,b,c, ...) thereby saving yourself and your users the hassle of a whopping two extra key-strokes. I know it's rather ri-donk-ulous but programmers tend to appreciate the motto "less is more".

  2. You can use 'a%b' or 'b%a' just make sure you adjust the above code accordingly.

As a final exercise see if you can create a single function such as:

gcd( some_list_where_length_>=_1 )
    ...do some stuff
    ...return the gcd