# Greatest Common Denominator

Imagine that you are nine and you’re going to 3rd grade math class. Your teacher asks for the greatest common denominator between 10 and 15. Everyone else is just as stumped as you are, but being gifted with the incredible ability to program computers, you decide to write a program to do it for you.

- 12 February, 2011 -
- Python -
- Tags :
- 3 Comments

Actually, GCD seems fairly complicated for 3rd grade math… meh, let’s assume that you’re brilliant

By definition:

the GCD of two or more numbers is the largest positive integer that divides the numbers without a remainder

Which we can translate directly into a loop. We start with the lesser of the two numbers as a candidate and test to see if it’s a common denominator (divides into both numbers without remainder), we then decrease the candidate until it becomes a common denominator.

### 1. Bruteforce it

# Brute force implementation def gcd(u,v): d = min(u,v) # Take the smaller of the two inputs while not ((u%d)==0 and (v%d)==0): d -= 1 # make sure that d isn't the denominator and reduce d return d

That condition looks really ugly, so let’s simplify it. We’re testing to see whether !(!A && !B) is true, which by DeMorgan’s law can be re-expressed as (!!A || !!B) === (A or B)

def gcd(u,v): d = min(u,v) while u%d or v%d: # demorgan's d -= 1 return d

But after a little bit of wikipedia-ing, I’ve found that Euclid have came up with a recursive definition of GCD that’s much more efficient:

A much more efficient method for finding the greatest common divisor than

that above was discovered by Euclid over two thousand years ago. Euclid’s

method is based on the fact that if u is greater than v then the greatest

common divisor of u and v is the same as the greatest common divisor of v

and u – v. Applying this rule successively, we can continue to subtract off

multiples of v from u until we get a number less than v. But this number is

exactly the same as the remainder left after dividing u by v, which is what

the mod function computes: the greatee:t common divisor of u and v is the

same as the greatest common divisor of 1) and u mod v. If u mod v is 0, then v

divides u exactly and is itself their greatest common divisor, so we are done.

### 2. Euclid’s Algorithm

# Euclid's method def gcd(u,v): if not v: return u else: return gcd(v, u%v)

or even more concise

def gcd(u,v): return not v and u or gcd(v, u%v) # but what if u is 0? meh...

Of course, if you’re really lazy:

### 3. The Python Way

from fractions import gcd # <_<

Pingback: Your Questions About Confidence Interval | Find Love Today()