Week 65 of 125
TAOCP 4.5.1 and 4.5.2
Sign up or sign in to tick these off and give this week a due date.
-
Knuth Knuth 4.5.1 Fractions
Exact rational arithmetic: keeping fractions in lowest terms with gcds, and doing it efficiently so intermediate numbers do not explode.
Time About 3 hours this week
Why it matters
Rationals are used in computer algebra, geometry kernels and anywhere floats are not exact enough.
Before you start
- 4.5.2 GCD idea from 1.1
- 4.3.1 Classical Algorithms
How to approach it
Implement a Rational type with add and multiply that reduces cleverly using gcds of partial terms, as the section suggests, and test it.
Exercises
This is a light section. Skim the exercises, do the ones rated 10 or under in your head, and spend the spare time catching up on earlier exercises you skipped.
Traps
- Reducing only at the end and overflowing in the middle.
-
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.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.