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 :)

Eclipse Juno

I recently downloaded the current version of the Eclipse IDE. It's called Juno, or 4.2 if you don't have the time to keep up with names (like myself).

I was very excited to use the new version. In the past every time I updated it seemed a host of bugs were fixed and life was good. The Groovy and Grails support generally improves dramatically between releases. 4.2 did not let me down in that area. The editors and over all support for Groovy and Grails are getting pretty good! :)

However, the inspiration for this post is not the good, because the good alone doesn't warrant a post. If the new features were amazing or something, sure a post is in order. That is not the case. Eclipse has updated the UI.... I'm all for pretty new UIs, but only if they work and don't take away from usability.

Previous versions of Eclipse handled screen splitting and tab dragging perfectly. I would change nothing. I have 3 displays, and I am constantly dragging tabs between them. I also drag tabs off to split up the editor on one display so I can see multiple files at once in the same editor.

Well, all that is now busted. I can't drag between editors anymore. Dragging at all seems to make Eclipse stutter and sometimes lock up for a few seconds, but it feels like eons. Now when you drag a tab off an editor, instead of being placed into another existing editor, one that's directly below your mouse, a new editing...window is created. If you hit ctrl+shift+r in that window, the file open dialog opens up, but when you select a file to open, it's opened in the original editor, not in the new window you created.....ARGHHHGHHH.

Lastly, Eclipse is a lot more sluggish now.. I mean it is a Java desktop application. So I allow for a certain amount of hesitation. With 4.2 though, I feel I am often waiting for the screen to repaint :(

So yeah, Eclipse for multiple monitors is pretty well busted. I hope it's fixed soon. Eclipse is the reason I have 3 displays...

Permutations and Combinations With Groovy

fac: work out the factorial of any positive integer

comobs: given n amount of things, and picking r amount from it, where order does not matter, how many combos are there?

permutations: give n amount of things, picking r amount from it, where order matters, how many permutations are there?

def fac = {it = it as BigInteger;  it <= 1 ? 1 : it * call(it - 1)}

// c(n,r) = n!/r!(n-r)!
// n = 52 cards  ; r = 5 cards per hand
// order doesnt matter!!
def combos = { n, r -> fac(n).divide(fac(r)*fac(n-r))}

// P(n,r) = n!/(n-r)!
// order matters!!
def permutations = { n, r-> fac(n).divide(fac(n-r))}

combos(52,5)
2598960

permutations(10, 2)
90