NUM Numbers and algebra Algorithm
Euclid's algorithm
Also known as: Euclid's algorithm · GCD · extended Euclidean algorithm · gcd
The oldest algorithm that still works every day: the greatest common divisor in a few divisions with remainder. It reduces fractions, computes RSA keys, chooses the teeth of gears, and, as it turned out in 2005, it also lays out the beats in the rhythms of drummers on different continents.
Take eight steps of a bar and three beats. Place the beats as evenly as possible, so that the gaps between them differ as little as possible. The result is x..x..x.: the tresillo, the rhythm of the habanera and of rockabilly. Five beats in eight steps is the cinquillo. Press “Listen” and move the sliders. On the right you can see how the program arrived at the answer. This is Euclid's algorithm, which is more than two thousand years old.
Look at the steps on the right. First there are three groups “x” and five groups “.”. Stick a dot onto each “x”, and two dots remain. Then stick the two remaining ones onto the three groups obtained, and one group remains, and that is it. Five and three, three and two, two and one: this is exactly the sequence of remainders that Euclid builds when looking for the greatest common divisor of eight and three. The connection was noticed in 2005 by the mathematician Godfried Toussaint. And the algorithm for laying out pulses itself had been devised two years earlier by the physicist Eric Bjorklund for the timing system of the SNS neutron source accelerator. He needed to place the pulses of the beam as evenly as possible: the same problem, only without drums.
The idea
Any common divisor of the numbers a and b also divides the remainder a mod b, and vice versa. So gcd(a, b) = gcd(b, a mod b). The remainder is smaller than the divisor, the numbers shrink quickly, and when the remainder becomes zero, the last non-zero number is the answer.
This is easy to see on a rectangle. The greatest common divisor of the sides a and b is the side of the largest square with which the rectangle can be tiled without gaps. Cut off from the rectangle as many squares of side b as fit: a strip of width a mod b remains. Any square that tiles the whole rectangle also tiles this strip. So the problem has become smaller, but the answer has not changed. Keep cutting until the strip disappears.
Enter the sides 1071 and 462: three steps, and the gcd is 21. Now press “Fibonacci 89 × 55”: each step cuts off exactly one square, there are nine steps, and the result is the famous spiral of squares. This is the slowest case, and we will come back to it.
Why it is right
If a = q·b + r, the common divisors of the pairs (a, b) and (b, r) are the same. In particular, gcd(a, b) = gcd(b, r).
If d divides a and b, it also divides r = a − q·b. If d divides b and r, it also divides a = q·b + r. The sets of common divisors coincide, so the greatest ones coincide too.
The remainders strictly decrease and are non-negative, so sooner or later the remainder is zero. At the last step gcd(g, 0) = g, and by the lemma this is the gcd of the original pair.
In Euclid's Elements (Book VII, Proposition 2) there is subtraction instead of division with remainder: the smaller is taken from the larger until the numbers become equal. The result is the same, but there may be very many subtractions: for the pair (10¹⁸, 1), a billion billion. Division with remainder does in one step everything subtraction does in q steps.
The extended algorithm
Euclid's steps can be run backwards to express the gcd through the original numbers. From 1071 = 2·462 + 147 and 462 = 3·147 + 21 we get 21 = 462 − 3·147 = 462 − 3·(1071 − 2·462) = 7·462 − 3·1071. In general:
For any integers a and b, not both zero, there are integers x and y such that a·x + b·y = gcd(a, b).
The extended algorithm finds these x and y on the way, without a backward pass. It keeps two equalities of the form a·x + b·y = r and subtracts from one the other multiplied by the quotient, exactly as the ordinary Euclid subtracts remainders. The main application is the modular inverse: if gcd(a, m) = 1, then a·x + m·y = 1, and modulo m this means a·x ≡ 1. Without this operation the RSA private key cannot be computed: it is exactly the inverse of the public exponent.
Code
The ordinary and the extended algorithm, the least common multiple and the inverse. The least common multiple is computed as a / gcd · b, not a·b / gcd: dividing first keeps the intermediate product from overflowing in Go.
Python has ready-made math.gcd, math.lcm and pow(a, -1, m) for the modular inverse. Go's standard library has no gcd for ordinary integers, only for big numbers, big.Int.GCD, and it is usually written by hand: three lines.
And this is the rhythm algorithm from the first scene. It prints each grouping step, and you can see how the numbers of groups repeat Euclid's remainders:
What it costs
Every two steps reduce the larger number at least by half: if r = a mod b, then r < a/2 (either b ≤ a/2 and the remainder is less than b, or b > a/2 and the remainder equals a − b < a/2). So there are O(log min(a, b)) steps.
The exact bound was found in 1844 by Gabriel Lamé: the number of divisions is at most five times the number of decimal digits of the smaller number. The worst case is neighbouring Fibonacci numbers: every quotient is one, and each step takes away as little as possible. The pair (89, 55) from the second scene needs nine divisions, and for numbers up to 10¹⁸ the worst case is 85 divisions, again neighbouring Fibonacci numbers, 679,891,637,638,612,258 and 420,196,140,727,489,673. This is one of the first theorems about the complexity of an algorithm at all, long before the words “complexity of an algorithm” appeared.
For very long numbers, where division is expensive, there is Stein's binary algorithm (1967): it manages with subtractions and shifts, using the fact that the gcd of two even numbers is twice the gcd of their halves. For numbers that fit in a machine word, the ordinary Euclid with division is almost always no worse.
Where it is used
- Fractions. Any rational number library,
fractions.Fractionin Python,big.Ratin Go, reduces a fraction by dividing by the gcd after each operation. - Cryptography. The RSA private exponent is a modular inverse, and the Chinese remainder theorem, which speeds up decryption, is also built on the extended algorithm.
- Gears. If the tooth counts of two gears are coprime, each tooth of one gear in time meets each tooth of the other, and wear is spread evenly. Such a pair is called a gear with a “hunting tooth”; how many turns pass before a pair of teeth meets again is told by the gcd, which is the first problem.
- Rhythms and schedules. Spread k events evenly over n slots: beats in a bar, pulses in an accelerator, ad impressions in a feed. This is the Euclid of the first scene.
History
The algorithm is written down in Euclid's Elements around 300 BC and was apparently known even earlier. Donald Knuth called it the granddaddy of all algorithms: it is the oldest non-trivial algorithm that has survived to our day and still works unchanged. Euclid applied it not only to numbers but also to line segments: in the tenth book of the Elements the same procedure checks whether two segments have a common measure. If the process never ends, the segments are incommensurable. By one account, this is how it was discovered in antiquity that the diagonal of a square is not measured by its side.
Problems
The first problem has gears and a check that you divide rather than subtract. The second needs the extended algorithm and a little thought about which of infinitely many solutions to choose.
The hunting tooth Two coins