The Oldest Algorithm Still in Production

Question

Two execution schedules fire every 1071 ms and every 462 ms. Find the coarsest common time grid, that is, gcd(1071, 462), by hand, explain why the algorithm you used is valid, and say roughly how fast it runs in general.

Accepted Answer

Euclid's algorithm. Repeatedly replace the pair by (smaller, remainder): 1071 = 2 cdot 462 + 147, qquad 462 = 3 cdot 147 + 21, qquad 147 = 7 cdot 21 + 0. The last nonzero remainder is the answer: gcd(1071, 462) = mathbf21. (Check: 1071 = 21 cdot 51, 462 = 21 cdot 22, and 51 and 22 share no factor.) Why it's valid. If d divides a and b, it divides a - qb = a bmod b; conversely if d divides b and a bmod b, it divides a. So the pairs (a, b) and (b, a bmod b) have identical sets of common divisors, hence the same greatest one. Each step preserves the answer while shrinking the numbers, and remainders strictly decrease, so it terminates. Speed. The remainder at least halves every two steps, so the run time is O(log) in the inputs, a 200-digit gcd takes hundreds of steps, not 10^200. The worst case (slowest shrinkage) is consecutive Fibonacci numbers (Lamé's theorem), because the quotient is 1 at every step, a pleasing echo of the golden ratio's status as the "most irrational" number. Where a desk meets gcds. The two schedules above coincide every mathrmlcm = frac1071 cdot 46221 = 23562 ms, gcd and lcm are one division apart, and alignment-of-cycles questions (batch jobs, exchange sessio

The Oldest Algorithm Still in Production

Problem

Your answer

Hints