Week 53 of 125
TAOCP 3.3.4 The Spectral Test
Sign up or sign in to tick these off and give this week a due date.
-
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.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.