Greatest Common Factor

Greatest Common Factor (GCF) is something you learn in grade school. It is still fascinating to me.

Greatest Common Factor, also known as Greatest Common Divisor is:

(from Wikipedia)

GCF of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.

You might have used GCF to reduce a fraction to its simplest form, also known as coprime (prime relative to each other).

GCF can be calculated a few ways. One fun way is to reduce both numbers to their prime factors. Then tally up what they have in common. Here are the prime factor trees for 1000 and 350.

The common prime factors between these 2 numbers are: 2 * 5² . So 50 is the GCF. Doing a prime factor tree for bigger numbers can take a while and be messy.

In Euclid's Elements exists an algorithm to compute the GCF much easier. In his time the concept of Real Numbers did not exist. So GCF was expressed geometrically. The GCD of two lengths a and b corresponds to the greatest length g that measures a and b evenly; in other words, the lengths a and b are both integer multiples of the length g.

Now days this idea is easier expressed with numbers. Here is the formula:

This can also be expressed with floored division instead of mod.

So, if you wanted to use this formula with pen and paper its easy. You divide 1000 by 350 (to use our example above) Then divide 350 by the remainder, then divide the remainder of that into the previous remainder an so on until you reach a division operation that produces no remainder. The divisor, or the number you used to divide with, that resulted in no remainder, is the GCF! YAY.

Lets look at a few implementations in Groovy. lameGcd iterates from the value of the smallest number down to 2 looking for numbers that will divide into both with no remainder. This means that in a worst case you would have to iterate from the value of num to 2.

def lameGcd = 
{ num, denom ->
 for(int i = num; i > 1; i--)
 {
  if(num%i==0 && denom%i==0) return i
 }
 return 1
}

We can do better using the Euclidean algorithm:

def edGcd = { num, denom -> !(denom%num) ? num : edGcd(denom%num, num) }

Here is a version that doesn't care which number is bigger:

def euclidDivisionGCD = { a, b ->
 def big = Math.max(a,b) 
 def small = Math.min(a,b)
 return !(big%small) ? small : call(small, big%small)
}

It's getting late. Next I'll carry on about Least Common Multiple :)