Sunday, 11 May 2014
What's Up With Euclid's Algorithm?!
Finding the greatest common divisor, gcd, of two numbers seems easy when you're dealing with something like 12 and 9 (gcd=3) or 72 and 36 (gcd=18). When you get to bigger numbers like 4155 and 5817 it becomes a little bit harder, but not for computers! Computers are proficient number crunchers and if we give them the algorithm to get something done, they'll do it. It just so happens that Euclid's Algorithm gives us a way of finding the gcd of two numbers, but before I lay down the steps I want to explain something first:
Lets say you have two integers X and Y with some greatest common divisor (I suppose any two numbers will have a gcd anyway, even if the gcd=1). And lets say X-Y=Z. It just so happens that Z has the same gcd as X and Y! So what we are saying is that gcd(X,Y)=gcd(Z,X)=gcd(Z,Y). If that was confusing, let's look at a simple example. So with 12 and 9 the gcd=3 and 12-9=3 so the greatest common factor between 3,9 and 12 is 3 (nothing's changed). Likewise with 42 and 12, the gcd=6 and 42-12=30 and the greatest common divisor of 12,42, and 30 is 6 (nothing's changed). Why? Because 42-12=30 is the same as saying 6*7-6*2=6*5 or 6*(7-2)=6*5 so clearly that greatest common divisor, 6, is there to stay because it gets factored out on the left and just gets multiplied by the simple subtraction inside the parentheses to produce the number on the right of the equation. The reason this is so good is that we can repeat the process of subtracting and whittling away at the numbers until we have the greatest common factor itself.
With 4155 and 5817, let's start by getting 5817-4155 which is 1662. They all share the same gcd but we only care about the smaller numbers (because soon enough we'll get to the gcd and won't be able to keep breaking the numbers down) so let's discard the 5817 and look at just 4155 and 1662. 4155-1662 = 2493 but we can do the subtraction again to get 2493-1662 = 831. Now we can look at just 1662 and 831 because all the way down the line, all of our numbers have shared the same greatest common divisor as our first numbers. 1662-831 = 831. What does this mean? Well usually after doing X-Y=Z we'd do Y-Z=V but here Y=Z which means after doing the subtraction 831-831 we'd get zero. We can't break it down any further and hence we know that the gcd(4155,5817) = 831. Another way of looking at it is that 1662 can be evenly divided by 831 and as we haven't skipped any larger numbers we know 831 must be the largest common divisor.
But subtraction is a bit laborious, because you need to keep subtracting away until you've got a number smaller than the number you're subtracting by. Here is where division comes in: if you have 13/4 you could work that out by having a counter which increments every subtraction by 4 you do. So 13-4=9 (counter = 1), and 9-4 = 5 (counter = 2) and 5-4 = 1 (counter = 3) and the answer is the counter value + 1/4 i.e. 3 and 1/4. The 1 in 1/4 is the remainder and just happens to be what you are left with in the above paragraph when you're left with a number which can't be subtracted by 4 to make a positive number. So the process of whittling down a number by doing X=X-Y repeatedly until Y>X and then returning X is really the same as finding the remainder of the division X/Y. Another way of describing the remainder (or modulo) of a division is X % Y = remainder.
So now we've worked out that the subtractions are just a long winded way of finding the remainder of X/Y. So X % Y = Z. Recalling what happens after Z is obtained, now you can do Y % Z = V and so on until your V is divisible by Z because at that point Z % V = 0 meaning the problem can't be broken down any further and as Z has the same greatest common divisor as your starting numbers, you've found the number which divides into Z which must be the greatest common divisor.
So with the above example, let's find gcd(5817,4155) using the remainder method:
X=max(5817,4155) //5817
Y=min(5817,4155) //4155
Z=X % Y // which is 1662
X=Y //4155
Y=Z //1662
Z=X % Y // which is 831
X=Y //1662
Y=Z //831
Z=X % Y // which is 0 so we've found the gcd
return Z // return 831
As you can see this algorithm is going to need some iteration:
gcd(a,b):
X=max(a,b)
Y=min(a,b)
do
Z=X%Y
X=Y
Y=Z
until Z=0
return Z
it's good to ensure X is the larger of the two values a and b and Y is the smaller because a small number divided by a big number will just produce a remainder that is the small number itself i.e. 4 % 19 = 4. HOWEVER as the 19 and the right 4 gets shifted to the in left in the equation, in the next iteration you'll have 19 % 4 anyway so the max and mins aren't necessary but they'll save you one iteration (and right now I'm not actually sure which method is more computationally efficient but using max and mins mimics how the average person would start off solving the problem).
ALRIGHTY so there's my intuition behind Euclid's Algorithm
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment