Add Me!Close Menu Navigation

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.

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 # <_<
Posted By Lee

Woosh

  • Dark Byte

    Nice, I have written a function to find the GCD of an array.

    C++
    [code]
    int GCD(int nsize, int* args) {
    int min = 2^32;
    for ( int i = 0; i < nsize; i++ )
    min = min 1 ) {
    int highest = 0;
    for ( int i = 0; i < nsize; i++ ) {
    int v = args[i] % min;
    highest = highest 0 )
    min–;
    else
    return min;
    }

    return 0; // No GCD exists
    }[/code]

    Lua
    [code]
    function math.gcd(…)
    local args = {…}; — Get the parameters
    local min = math.min(unpack(args)); — find the smallest value (the GCD will at least be this small)

    while ( min > 1 ) do
    local highest = 0;
    for _, v in ipairs(args) do
    if ( v%1 ~= 0 ) then
    return -1; — ALL paramets MUST be integers
    end
    v = v % min;
    highest = highest 0 ) then
    min = min – 1;
    else
    return min;
    end
    end

    return 0; — No GCD exists
    end[/code]

    • http://phailed.me/ Phailure

      haha, nice

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