The test that ranks the generators

The first rung on this ladder establishes that consecutive outputs of a linear congruential generator lie on a small family of parallel planes, and that no amount of statistical testing would reveal it because no statistical test asks that question. It leaves an obvious follow-up unanswered: given that every such generator has the defect, how does one tell a bad generator from a tolerable one?

The answer is a single number, it is computed rather than measured, and it ranks generators completely.

The structure, restated #

If $x_{n+1} = a x_n \bmod m$, then any whole numbers $q_1, q_2$ with

$$q_1 + q_2 a \equiv 0 \pmod m$$

satisfy $q_1 x_n + q_2 x_{n+1} \equiv 0 \pmod m$ for every $n$. So every pair of consecutive outputs lies on one of the lines $q_1 u_1 + q_2 u_2 = k$, with $u = x/m$ and $k$ a whole number.

Those lines are parallel and evenly spaced, and the spacing is

$$\frac{1}{\sqrt{q_1^2 + q_2^2}} = \frac{1}{|q|}.$$

A short $q$ means widely separated lines, which is bad; a long $q$ means the lines are close together and the points cover the square more evenly.

So the quality of the generator in two dimensions is $1/|q|$ where $q$ is the shortest non-zero vector satisfying the congruence. Finding it is a shortest-vector problem in a two-dimensional lattice, which is exactly the lattice of vectors annihilating the generator.

Why this is a lattice question #

The vectors $q$ with $q_1 + q_2 a \equiv 0 \pmod m$ form a lattice: closed under addition and under integer multiples, and generated by two basis vectors — for instance $(m, 0)$ and $(-a, 1)$.

That reframing is what makes the problem solvable. The generator’s quality is a shortest vector in a lattice of determinant $m$, and the theory of lattices supplies both bounds and algorithms.

The bound is the more informative half. Minkowski’s theorem — that a symmetric convex region of large enough area must contain a lattice point other than the origin, which is the counting argument a lattice makes available — gives a shortest vector of length at most a constant times $\sqrt{m}$ in two dimensions, and in $d$ dimensions at most a constant times $m^{1/d}$. So the spacing between hyperplanes is at least $c \cdot m^{-1/d}$, whatever the multiplier — no linear generator can be good in high dimensions, and the limit is a theorem rather than a defect of any particular one.

Putting numbers on it: a generator with modulus $2^{32}$ has, in ten dimensions, at most about $2^{3.2} \approx 9$ per unit spacing, meaning fewer than a few thousand hyperplanes covering the whole ten-dimensional cube. A simulation whose behaviour depends on ten consecutive values is therefore sampling a few thousand hyperplanes rather than a cube, however the multiplier is chosen.

It is worth separating the two criteria clearly, because they are often conflated and only one of them is hard.

Period is a question about the orbit’s length and is settled by the Hull–Dobell conditions: with modulus $m$, the generator has full period exactly when the increment is coprime to $m$, the multiplier minus one is divisible by every prime factor of $m$, and by four if $m$ is. Those are checkable in a moment and every published generator satisfies them.

Spacing is a question about where the orbit’s points sit, and two generators with identical full periods can differ by a factor of ten in it. A generator can visit every value in the modulus — the strongest possible statement about coverage in one dimension — and still put every consecutive pair on fifteen lines.

So the period says the points are all present and says nothing about their arrangement, which is the distinction the whole rung rests on.

The test, and what it is not #

The spectral test is: compute the shortest annihilating vector in dimensions two through eight or so, take the reciprocal of its length in each, and compare against the Minkowski bound for that dimension. A generator scores well when it is close to the best possible for its modulus in every dimension.

Three properties make it the right instrument, and it is worth contrasting each with what a statistical battery offers instead.

It is exact. No sampling, no statistics, no thresholds. The answer is a number computed from $a$ and $m$ by a lattice reduction, and running it twice gives the same answer.

It is structural. It measures the thing that is actually wrong with the generator, rather than a consequence of it that a test might or might not detect. Every statistical test is a guess about which consequence to look for; this looks at the cause.

And it is a total order. Two generators can be compared. Statistical batteries produce a table of pass and fail against dozens of tests, and comparing two tables is a judgement; comparing two numbers is not. That matters practically: a designer choosing a multiplier can search a large space and keep the best, which is what an exhaustive search over a finite structure makes possible and what a test requiring a simulation per candidate does not.

What it does not do is certify a generator as random. It certifies that the lattice defect is as small as the modulus allows, and says nothing about any other structure. A generator can pass the spectral test in every dimension and still be trivially predictable, which is the next rung’s subject.

RANDU, and why the test matters #

The standard cautionary example is worth the space because it is a case where the test would have caught a defect that a generation of simulations did not.

IBM’s RANDU, shipped in the 1960s and used for a decade, is $x_{n+1} = 65539\,x_n \bmod 2^{31}$. The multiplier was chosen because $65539 = 2^{16} + 3$, which makes the multiplication cheap.

It also makes $x_{n+2} = 6x_{n+1} - 9x_n$ exactly, modulo the modulus — a relation with tiny coefficients, so the annihilating vector $(9, -6, 1)$ has length under eleven. Consecutive triples therefore lie on fifteen planes, in a cube that ought to be filled.

The spectral test reports that immediately. No statistical battery of the era did, and results computed with RANDU — particularly Monte Carlo estimates in three or more dimensions — were quietly wrong for years.

The lesson is not that RANDU was badly designed but that it was designed against the wrong criterion. Cheap multiplication and a long period were the goals; the structure was not measured because nobody was measuring it.

Reading a bad multiplier by inspection #

Some multipliers can be condemned without computing anything, and knowing the signs is worth more than the algorithm for most purposes.

A small multiplier is bad. If $a$ is small then $(a, -1)$ nearly annihilates: $a x_n - x_{n+1} = -c$ exactly for the un-reduced values, so the vector $(a, -1)$ has length about $a$, and the spacing is about $1/a$. A multiplier of ten puts consecutive pairs on about ten lines.

A multiplier near a simple fraction of the modulus is bad. If $a \approx pm/q$ for small $p$ and $q$ then $q a - p m$ is small, so $(qa \bmod m, \ldots)$ gives a short vector. That is why the search for a good multiplier is a search for one badly approximated by fractions with small denominators — the same condition that makes a number “as irrational as possible”.

And a multiplier with a short binary expansion is bad, which is the RANDU case: $2^{16}+3$ has a two-term expansion, so a relation with coefficients of size a few emerges after two steps. The multiplication is cheap for exactly the reason the generator is bad, which is an unusually direct trade and was not recognised as one at the time.

Every one of those is the same defect: a short relation among the powers of $a$ modulo $m$. The spectral test is the systematic search for the shortest such relation, and the rules of thumb are the cases where one is visible.

What good looks like #

Applying the test to the well-known generators gives a clear ranking and a clear ceiling.

A modulus that is a power of two is a handicap. The lattice inherits the modulus’s factorisation, and the low-order bits of the output have short periods — the last bit alternates, the last two bits cycle with period four, and in general the last $k$ bits have period at most $2^k$. That is a second defect on top of the lattice one, it is invisible to anybody using the high bits, and it is catastrophic for anybody who takes the output modulo a small number, which is the obvious way to get a random choice from a short list. A prime modulus avoids all of it, at the cost of a more expensive reduction.

The multiplier must be large and structureless. Any multiplier expressible in a few bits gives a short vector, and so does any multiplier close to a simple fraction of the modulus.

And even a perfect score is bounded. Minkowski’s bound is the ceiling and it falls off as $m^{-1/d}$, so the only way to be good in high dimensions is a very large modulus. That is precisely why the generators now in use are not linear congruential at all: the Mersenne twister has a state of nineteen thousand bits, and the modern successors of it have states of hundreds.

Enlarging the state is worth understanding as the response it is. A generator whose state is a single number modulo $m$ has a lattice of determinant $m$ and cannot escape the bound; a generator whose state is many numbers has a much bigger lattice and a correspondingly better bound. The fix is not a cleverer multiplier but more memory, and that is available now and was not in 1965, which is most of why the subject moved.

That small case is worth keeping in mind as the reference. At modulus two hundred and fifty-six the defect is obvious to the eye; at modulus $2^{31}$ it is invisible in a scatter plot of any size a person can look at, and the points look perfectly uniform. The defect does not shrink with the modulus — the spacing falls as $m^{-1/2}$ in two dimensions and the number of points a plot can show falls faster — so the eye stops being able to detect what the arithmetic still says is there.

What it costs #

Computing it is a shortest-vector problem, which is easy in low dimensions and hard in high ones — the general problem is NP-hard. In practice the dimensions of interest are small enough for exact algorithms, and the figures here search directly over a bounded box.

It measures one dimension at a time and a simulation uses many. A generator can score well in dimensions two through six and badly in seven, and which dimension matters depends on the simulation. The usual practice is to require a good score in every dimension up to eight and hope, which is honest and is not a guarantee.

And it is silent about non-linear generators. A generator with no linear recurrence has no annihilating lattice, so the test does not apply. That is not a defect of the test but a statement of its scope, and it means the modern generators are evaluated by other means — mostly by statistical batteries, which is a step backwards in rigour justified by there being nothing better.

Who built it #

The test is due to Coveyou and MacPherson in 1967, and its promotion to the standard tool is Knuth’s, in the second volume of The Art of Computer Programming, where it occupies a long section and is presented — correctly — as the only test worth running first.

The circumstances are worth recording. By the mid-sixties there were dozens of published generators, each accompanied by a table of statistical tests it passed, and no way to compare two of them. Coveyou and MacPherson’s contribution was to notice that the question has an exact answer, because the structure is a lattice and lattices have shortest vectors.

Knuth’s assessment is the one that stuck: he describes the statistical tests as necessary and the spectral test as the one that distinguishes the good generators from the bad, and notes that every generator known to have failed in practice also fails the spectral test — while several generators that pass every statistical battery fail it.

That last observation is the argument for the whole approach. A test that catches every known failure and additionally flags generators nobody had yet caught out is a better test than the ones that caught none of them until the damage was done.

What the pictures cannot show #

Two dimensions are the only ones that fit on a page. The test is run in dimensions up to eight or more, and the defect it detects is often invisible in two — a generator can look perfectly uniform in the plane and lie on a few dozen hyperplanes in six dimensions. The figures show the case where the phenomenon is visible, which is the case that matters least.

The shortest vector is found by search and reported as a number. The lattice it lives in is not drawn, and the reduction that finds it — Gauss’s algorithm in two dimensions, LLL above — is an algorithm rather than a picture.

A scatter of a thousand points cannot show a family of a thousand lines. Where a generator is good the lines are close enough together that the picture is a uniform grey, and the figure’s assertion that the lines exist is doing all the work. The pictures are informative about the bad cases and uninformative about the good ones, which is the opposite of what a reader wants and is unavoidable.

And the spacing is a property of the family, not of the points. The figure measures which lines are occupied and checks they are consecutive; the spacing itself comes from the vector’s length. A drawing showing points on lines does not display the distance between the lines in any way a reader can measure off the page.

Where the ladder goes next #

The next rung asks a sharper question than “how evenly are the points spread”: given a few outputs, can the rule be recovered? The answer is yes and it takes four numbers, which is a failure of a completely different kind from the lattice defect and is not measured by any spectral test.

Named here as a debt: lattice reduction itself — the LLL algorithm, which finds short vectors in high dimensions and is the tool the spectral test uses above three dimensions. It has a life far outside this subject and this rung uses it without drawing it.

Also unwritten and worth naming: the equidistribution criterion the Mersenne twister is designed against, which asks that every pattern of bits at a given depth occur equally often — a different structural measure, exactly stated, for a generator with no lattice. It is what replaced the spectral test rather than what extends it.

Sideways, the lattice of annihilating vectors is the same kind of object as the lattice of Gaussian integers, and the question of how well a real number is approximated by fractions — which decides whether a multiplier is bad — is the continued fraction’s subject.

What is worth carrying away #

A structural measurement beats a battery of consequences, when a structural measurement is available.

Every statistical test of a generator is a guess about which symptom to look for, and a generator can be built to pass any fixed list. The spectral test measures the disease: the lattice is what a linear recurrence is, and its shortest vector is the exact statement of how badly the generator fails to fill space.

The habit worth taking is to look for the invariant the construction cannot avoid. A linear recurrence cannot avoid having an annihilating lattice, so measuring that lattice measures every generator of the family at once — and the bound on how good it can be is then a theorem rather than an experiment.