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.
Actually, GCD seems fairly complicated for 3rd grade math… meh, let’s assume that you’re brilliant
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 # <_<