TAOCP Vol 2: Seminumerical Algorithms · Week 65
TAOCP 4.5.1 Fractions: reading guide
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.