TAOCP Vol 2: Seminumerical Algorithms · Week 65
TAOCP 4.5.2 The Greatest Common Divisor: reading guide
Euclid again, now in depth: the extended algorithm for finding coefficients, the binary gcd algorithm that uses only shifts and subtraction, and gcd for multiple-precision numbers.
Time About 7 hours this week
Why it matters
Extended Euclid gives modular inverses, needed in RSA and hashing. Binary gcd is a good example of trading division for cheap operations.
Before you start
- 1.1 Algorithms
- 4.5.1 Fractions
How to approach it
Implement Euclid, binary gcd and extended Euclid. Benchmark the first two on 64-bit numbers. Use extended Euclid to compute modular inverses and check them.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Sign handling in extended Euclid coefficients.