About This Site
Game Theory Section
A Theorem on Finite Abelian Groups
On Rectangular Tilings
The Twelve-Note Scale
The Pentagon Knot
The Euclidean AlgorithmIf you have two whole numbers, a and b, sometimes you'd like to find the largest number that divides evenly into both of them. That number is called the greatest common divisor, or GCD, and is usually written in symbolic form as (a,b). What the Euclidean algorithm is is an efficient way of finding GCDs.
That's the most explicit example of a program yet! To see how it works, let's try a = 1309 and b = 2387.
So, there's the answer … (1309,2387) = 77. By the way, that first step is kind of stupid, isn't it? Normally you'd avoid it by setting a to the larger number right at the start, but the algorithm works fine even if you don't.
What are GCDs good for? Well, they're pretty fundamental, so asking what they're good for is sort of like asking what addition is good for. Nevertheless, here are a few random things that come to mind.
Next Block, The
Twelve-Note Scale, The
@ November (2005)