TAOCP Vol 2: Seminumerical Algorithms · Week 53
TAOCP 3.3.4 The Spectral Test: reading guide
The most important test for LCGs: in t dimensions, successive tuples from an LCG lie on a set of parallel hyperplanes, and the spectral test measures how far apart those planes are. Knuth gives an algorithm to compute it and tables of good and bad multipliers.
Time About 9 hours this week
Why it matters
This explains disasters like IBM's RANDU, whose triples fall on just 15 planes. It is the reason you should not trust a generator just because its 1D histogram looks flat.
Before you start
- 3.2.1 The Linear Congruential Method
- Basic linear algebra (vectors, dot products)
How to approach it
Before reading, plot (X_n, X_{n+1}) for a small LCG and see the lines. Plot RANDU triples in 3D. Then read the spectral test algorithm for the ideas. Following every step of the algorithm is optional.
Exercises
Implementing the spectral test algorithm itself is a worthy stretch goal. Otherwise do the low-rated exercises.
Traps
- Getting lost in lattice-reduction details. The picture is what matters.