TAOCP Vol 2: Seminumerical Algorithms · Week 51
TAOCP 3.3.2 Empirical Tests: reading guide
A battery of concrete tests for random sequences: equidistribution, serial pairs, gaps, poker hands, coupon collecting, permutations, runs up and down, maximum of t values, and collision tests.
Time About 8 hours this week
Why it matters
These are the ancestors of modern test suites like TestU01 and PractRand. Writing a few yourself gives you a feel for how generators fail.
Before you start
- 3.3.1 General Test Procedures
How to approach it
Pick three tests (gap, poker, runs are good choices) and implement them against both a decent generator and a bad LCG. You do not need to implement all of 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
- The runs test has correlated statistics; Knuth explains why a plain chi-square is wrong there. Read that part carefully.