The Euclidean Algorithm is one of the first algorithms ever written down. It is a darling of computer science. The algorithm cleverly reveals the greatest common divisor of two natural numbers. Despite its ancient origins, it is still well-used today (and not just for teaching). It can determine when two numbers are relatively prime – ie, when their greatest common divisor is one – which has important modern applications in cryptography. And it does so efficiently.

Here is a cute implementation:

def gcd(a,b):
    return a if b == 0 else gcd(b,a % b)

(NB. Error checking omitted for clarity.)

Look ma, recursion! To spell it out, when b is zero, then gcd(a,b) = a. When b is non-zero, then gcd(a,b) = gcd(b, r), where r is the remainder of a divided by b. Let’s do a short example: gcd(12, 8). We have:

gcd(12, 8) = gcd(8, 4) = gcd(4, 0) = 4

Ok, so what the heck is going on here? The gcd algorithm is deceptively simple looking. However, it leverages some rather deep properties of the natural numbers.

First, a little background. The titular Euclid, that crafty fellow, once proved something called the Fundamental Theorem of Arithmetic, which says that any number can be expressed (uniquely!) as the product of primes. For example,

12 = 2 x 2 x 3 = 4 x 3
8 = 2 x 2 x 2 = 4 x 2

You can see by inspecting the prime factors that the gcd is 4. But factoring numbers is computationally difficult, especially when they get larger. The gcd algorithm is so efficient (and remarkable) in part because it doesn’t have to do any factoring!

One useful fact is that when a number divides x and y, that number also divides x + y and x – y. You can see this by playing around with prime factors again. In the example above:

12 – 8 = 4 x 3 – 4 x 2 = 4 x (3 – 2)
12 + 8 = 4 x 3 + 4 x 2 = 4 x (3 + 2)

You can see that 4 is a factor not only of 12 and 8, but also 12 + 8, and 12 – 8. Still with me?

Ok, one other thing to get under your belt is the division theorem. It says we can come up with a unique whole number quotient q and remainder r for any natural number division a / b. That is, a = qb + r for some unique whole numbers q and r, where 0 <= r < b.

Finally, we can write out step by step what is happening in the Euclidean algorithm. We start with the arguments a and b, and put a row in the table which shows the current arguments along with what is computed (ie, the remainder a % b). We add a row for each recursive invocation.

step a b a % b
0 a = q[0] b + r[0]
1 b = q[1] r[0] + r[1]
2 r[0] = q[2] r[1] + r[2]
… etc …
n-1 r[n-3] = q[n-1] r[n-2] + r[n-1]
n r[n-2] = q[n] r[n-1] + r[n]
n+1 return r[n-1]

At each step, we pass in as arguments to the gcd function the values in columns a and b, and we compute the remainder a % b of their division and, if we want, the quotient, but we can ignore the quotient for now. Wash, rinse, repeat.

Let’s check out gcd(12, 8):

step a b a % b
0 12 = 1 8 + 4
1 8 = 2 4 + 0
2 return 4

In the nth iteration, the final remainder, r[n], is zero. Why is this? It’s because the remainder r of a division such as a = q b + r is strictly less than b, so the arguments shrink inexorably throughout the computation, and eventually you get down to zero.

In row n, where r[n] = 0, the dividend and divisor are r[n-2] and r[n-1], so we know that r[n-1] divides r[n-2] evenly (since there is no remainder to the division!) And clearly r[n-1] divides itself. So that means r[n-1] divides r[n-3] too, since it divides both terms of the sum which defines it (see row n-1). Likewise, we can work all the way back up the call stack in order to say that r[n-1] divides both the original arguments a and b as well.

Wait! We still don’t know whether that final non-zero remainder r[n-1] is the greatest among all possible common divisors. We do know that divisor r[n-1] is <= gcd, by definition of gcd. But we need to prove one more statement: ANY common divisor of a and b divides ALL the remainders r[i] of the algorithm.

ORLY? Well, just look at the procedure above and notice how the first remainder can be written r[0] = a – q[0] b. So anything that divides a and b must divide r[0]. Likewise, r[1] = b – q[1] r[0], so anything that divides b and r[0] must divide r[1]. Following the turtles all the way down the rabbit hole: any common divisor of a and b divides ALL remainders r[i].

One common divisor in particular is the gcd. Since it divides r[n-1] in particular, we can say that gcd <= r[n-1].

But if gcd <= r[n-1] and r[n-1] <= gcd, doesn’t that mean they are equal? Oh yes indeedy-do it does. Quod erat demonstratum, baby!

PS: for some visual intuition of the algorithm, check out the line-segment drawings in the top right hand corner of the Wikipedia entry.

Per my brother‘s suggestion, I decided to move my blog to a top-level domain.  While I’m at it, I thought, I might as well figure out how to host my own WordPress install. That way I can have handy control over the plug-ins, so I can do awesome things like code coloring:

#include <iostream>

void main() {
  std::cout << "Hello syntax highlighting!\n";
  exit(0);
}

I’m using Codecolorer. I also decided I need more control over my theme, so I switched to Suffusion, which is extremely configurable. One thing that puzzled me a bit was to stop flush-justifying all the text. The answer: in the Dashboard, go to Appearance > Editor (to get at the CSS), and find ‘justify’ and replace it with ‘left’.

Ok, so back to domain name.  I  purchased mine, adamdklein.com, from Namecheap for, you guessed it, cheap.  I’m not sure it’s a blessing or curse to share my name with so many other Adam Klein’s, but in college I once got a birthday check from another guy’s grandmother.  I’m curious if I could have cashed it legally –

Then I got some reasonable hosting from DreamHost, which has a one-click install of WordPress.  I think I’m sharing a web server instance on IIS, because setting up my WordPress install at first led to some weird IIS errors.  But now obviously it’s ok. They have some helpful tutorials online.

Oh yeah, the final thing was to export my old blog content into an XML file which I then ftp’d to my blog site directory at DreamHost where I could then import it into the new WordPress instance.  Worked like a charm!

I just “figured out” (read: noticed) how to enable shortcut keys in GMail.

Inspired I see in part by Vim key bindings:

  • ‘j’ for down
  • ‘k’ for up
  • ‘o’ for open
  • ‘#’ for delete
  • ‘g i’ for go to inbox.
  • ‘l’ for label.

My efficiency just shot up 95%!

I have two hard disks on my new iMac:

– solid-state disk: 256Gb. Core operating system files and application installs.
– regular HD: 1Tb. User files and media.

I moved my user directory from /Users/adam on the SSD disk, where it was installed by default, to a new folder (/adam) on the secondary hard drive (/Volumes/Macintosh HD 2). This caused problems when I started doing Unix-ish things. Especially with Python. Python does NOT like spaces in your directory.

I soft-linked the original directory (/Users/adam) to the new directory (/Volumes/Macintosh HD 2/adam) using 

ln -s ~ /Users/adam

. I then (re)set my user directory in OS X to /Users/adam.  Still, some stuff “saw” the aliased directory /Volumes/Macintosh HD 2/adam.  In the end, I renamed my “Macintosh HD” directories – their factory-installed names – to “HD1” and “HD2”. Problem solved, so far.

© 2014 Adam Klein's Blog Suffusion theme by Sayontan Sinha, modified by Adam :)