Fifteen Planes
Every test anybody thought to run on this generator, it passed. The mean is right, the histogram is flat, consecutive pairs fill the square. Then somebody looked at three numbers at once.
A generator, its tests, and the dimension nobody checked
1 Turn the handle and take some numbers
0.493080 0.943686 0.224398 0.853219 0.099726 0.919386 0.618783 0.438229
RANDU is xn+1 = 65539 · xn mod 231. That is the whole generator. It shipped with IBM's scientific subroutines and a great many results were computed with it.
2 Run the tests anyone would think to run, and watch it pass
Mean 0.50160, against 0.5. Widest bin over narrowest, 1.065, against 1. On these two, RANDU passes.
3 Look at triples instead of pairs
On the left, every consecutive pair plotted as a point in a square. On the right, every consecutive triple, viewed along the direction the arithmetic below says the structure lies in. Same numbers, both times.
4 Count the planes, and work out why there are that many
65539 = 216 + 3, so 655392 = 232 + 6·216 + 9. And 232 is 0 modulo 231, which leaves xn+2 = 6xn+1 − 9xn. Every triple therefore satisfies 9a − 6b + c = 0, and the only freedom left is which whole number the left side lands on.
Every one of 19,998 triples satisfies the relation, and they land on 15 distinct planes.
Fifteen planes. Three-dimensional space, twenty thousand points, and they occupy fifteen flat sheets with nothing at all in between. Nothing in the two tests above could see it, because neither of them ever looked at three numbers at once.
Checked when this page loaded, on 20,000 draws: every one of RANDU's 19,998 consecutive triples satisfies 9a minus 6b plus c equals zero, modulo 2 to the 31, with 0 exceptions, and the number of distinct planes they land on is 15. Run the same check against mulberry32 and 0 of its 19,998 triples satisfy the relation at all, which is what a generator that is not sitting on this lattice looks like.
The tests were not wrong, they were the wrong shape
A mean near a half says the numbers are centred. A flat histogram says no single value is favoured. Both are statements about one number at a time, and a generator can satisfy every one-dimensional test there is while its consecutive outputs are locked to each other.
Pairs are the obvious next step and RANDU passes that too, which is the part worth sitting with: the square above genuinely looks like noise. The structure needs three numbers to show up, and until 1968 nobody was looking there.
Why fifteen and not sixteen
The relation says 9a − 6b + c is a whole multiple of the modulus. Divide through and the quantity 9a − 6b + c, with each of a, b and c between 0 and 1, can only run from −6 to 10. That is sixteen whole numbers, and the count above is fifteen, because the extreme ones need corners of the cube the generator never reaches. The page counts what actually occurred rather than taking the arithmetic's word for it, which is the difference between a bound and a measurement.
This is the shape of CRC's argument, upside down
CRC says: here is a guarantee, and here is the exact edge where it stops. This says: here is a thing that looked correct from every angle anybody checked, and was degenerate in the first one they did not. Both are worth more than a probability, and both are settled by exhausting something rather than by arguing.
There is a second connection and it is closer to home. Backoff runs a generator, and its source says in as many words that the generator's quality is irrelevant there because every claim on that page is checked against a closed form instead. That sentence is true. This page is where it gets looked at: switch the generator above and the same twenty thousand draws stop lying on a lattice.
What is real here, and what is not
The paper that named this was not read
George Marsaglia, Random numbers fall mainly in the planes, Proceedings of the National Academy of Sciences 61(1):25–28, 1968, is where the general result lives: the outputs of any linear congruential generator, taken n at a time, lie on a small number of parallel hyperplanes. It has not been opened here, and the attempts are worth listing rather than summarising: the journal's own article page and its PDF, the PubMed Central article and its PDF, the same PDF through NCBI, and Europe PMC's article page and its full-text endpoint. Every one returns a shell that needs JavaScript, a download page gated behind a cookie, or a refusal. The bibliographic details are confirmed across catalogues; the text is not read.
Nothing on this page rests on it, which is the reason it can say so plainly. The relation is derived from the multiplier three lines above, and the count of planes is produced by running the generator here. A citation is where an idea came from, and a measurement is what this page offers instead of trusting one.
Fifteen is counted, not looked up
The number is arrived at twice on this page and both times by arithmetic. The bound comes from the relation and is sixteen; the count comes from running the generator and is fifteen. If they ever disagreed with what is drawn above, the drawing is made from the same pass that produces the count, so they cannot.
The seed must be odd, and the page keeps it that way
RANDU's modulus is a power of two, so an even seed shares a factor with it and the sequence degenerates further and dies short. The slider only offers odd seeds. That is a real property of the generator rather than a convenience: a reader who fed it an even number would see something worse than the planes and learn the wrong lesson from it.
The comparison generator is not being called good
mulberry32 fills the cube at this scale and that is all this page claims for it. It is a small non-cryptographic generator, it has a finite period, and it fails its own tests further out and in higher dimensions than anything drawn here. Every generator does somewhere. The lesson is not that this one is safe, it is that a test you did not think to run is not evidence.
Nothing here is about cryptographic randomness
Predicting the next number is a different requirement from filling space evenly, and a generator can do the second perfectly and fail the first completely, which every generator on this page does: give anyone two consecutive outputs of RANDU and the rest of the sequence follows. If the question is whether an adversary can guess it, none of this is the measurement you want.
The date is the paper's, not the generator's
1968 is when the planes were shown, not when RANDU was written. Sources give its use as the 1960s and 1970s without pinning an introduction year, and rather than invent one the roster is dated by the result. That is the same choice CRC makes at 1961.
Sources
- George Marsaglia, Random numbers fall mainly in the planes, PNAS 61(1):25-28, 1968, for the general result this machine is one instance of. Cited and not read; the ledger above lists every route tried
- RANDU, for the recurrence, the derived relation between three consecutive values, the count of fifteen planes and Knuth's assessment of it
- Linear congruential generator, for the family this belongs to and why the modulus and multiplier were chosen