TAOCP Vol 2: Seminumerical Algorithms · Week 52
TAOCP 3.3.3 Theoretical Tests: reading guide
Instead of running a generator, analyze it mathematically: for example, compute the serial correlation of an LCG exactly from its parameters. This brings in some heavy number theory, including Dedekind sums.
Time About 5 hours this week
Why it matters
Honestly, this is one of the more specialized sections for a working programmer. The takeaway is that you can sometimes prove a generator is bad without running it.
Before you start
- 3.3.2 Empirical Tests
- 1.2.4 Number theory
How to approach it
Read for the main results and the intuition. It is fine to skim the Dedekind sum derivations. Spend the time you save on finishing 3.3.2 implementations.
Exercises
Do the lower-rated exercises only; most of this section's exercises are M or HM and quite hard. 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
- Burning out here. It is fine to skim.