  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]

• haha, nice