Fifteen Planes
Every test on this page, this generator passes. The mean is right, the histogram is flat, consecutive pairs fill the square. Then somebody looked at three numbers at once.
New to testing a random number generator? Start here
A generator that is not random can still pass every test you thought to run. Its numbers look evenly spread, they average correctly, and consecutive pairs show nothing.
The catch is that structure can hide in a dimension you did not look at. Take the numbers three at a time as coordinates in space and a generator with hidden regularity does not fill the space: every point lands on one of a small number of flat sheets. Nothing about that is visible one number at a time.
Numbers in a fixed-size box
A number on paper can be as long as it needs to be. A number in a computer gets a fixed number of digits and no more, so there is always a largest one it can hold and always a smallest difference it can tell apart.
Almost everything surprising about computer arithmetic follows from that. What happens when you count past the largest value depends on which kind of number it is: a fixed-width integer wraps round to the smallest, and a floating-point number goes to infinity instead. A value too fine for the gap is not rejected, it is rounded to the nearest one that fits, and then the rounding is added to the next rounding. These are not faults in the machines here. They are the edges of the box, and the machines are what people built to live inside it.
The machine for this idea on its own is Two's Complement, if you would rather press it than read about it.
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 modulo 231, which is the form the check below tests. Over the integers that reads 9a − 6b + c = k·231, and the only freedom left is which whole number k is.
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 this coarse pairwise occupancy check too, which is the part worth sitting with: the square above genuinely looks like noise. The structure needs three numbers to show up. People were already looking: Coveyou and MacPherson published the spectral test for exactly this lattice structure in 1967. What Marsaglia did in 1968 was make it impossible to ignore.
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.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| RANDU's mean over 20,000 draws is 0.5016 and its 10 histogram bins differ by a factor of 1.065 | yes | it passes the tests anybody would think to run, which is why it shipped and was used for years |
| every one of its 19,998 triples lands exactly on one of 15 planes | yes | 9x(n) - 6x(n+1) + x(n+2) is a whole multiple of 2^31 every time; the page counts the triples that satisfy it rather than assuming they all do |
| the identity holds on all 198 triples tested directly in the generator's own units | yes | 65539 is 2^16 + 3, so squaring it gives 6 times 65539 minus 9, and the recurrence folds into three terms; that is the whole reason |
| a modern generator puts 0 of its 19,998 triples on those planes | yes | the same test on a generator that does not have the flaw, because a check that cannot come out the other way is not a check |
| in two dimensions those same numbers fill 400 of 400 cells and look fine | yes | the collapse needs three dimensions to see, which is why it survived years of people looking at scatter plots of pairs |
What is real here, and what is not
The eight numbers are not the first eight
Seed 1 is a small number, and a small number multiplied by 65539 a few times is still a small number: the opening outputs read 0.000031, 0.000183, 0.000824. Those look broken, and this page's whole argument is that RANDU looks fine until you take triples. So the display skips the first hundred outputs and shows the hundred-and-first onward. Everything measured uses the full draw from the seed rather than the skipped view: the mean, the histogram, the pair occupancy and the plane count. The label says eight of them rather than the first eight, which was true and was not enough: an outside reader recomputed the recurrence from the seed printed beside it and found the offset. It is stated here now.
The paper that named this, read at last
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 went unread here for a long time, and the routes that failed are worth keeping, because they are the ones anybody would try first: 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 of those returns a shell that needs JavaScript, a cookie wall, or a refusal, and PubMed Central does it to a real browser as readily as to a fetcher. The one that works is Europe PMC's render endpoint, which serves the four pages as they were printed, and it is archived here now. Marsaglia's own sentence for what this page draws: if n-tuples of the generator's output “are viewed as points in the unit cube of n dimensions, then all the points will be found to lie in a relatively small number of parallel hyperplanes”, and they are “about as randomly spaced in the unit n-cube as the atoms in a perfect crystal at absolute zero”.
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. Read, through Europe PMC's render endpoint after six other routes refused; the ledger above lists them
- 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