Generator

256 consecutive pairs from xₙ₊₁ = 137xₙ + 187 mod 256

A generator in the computation library, called 70 times across 14 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

lcg is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

256 consecutive pairs from xₙ₊₁ = 137xₙ + 187 mod 256. Consecutive outputs of a linear congruential generator plotted as points of a square, falling on a small family of evenly spaced parallel lines.

How far a filter spreads a generator's output

Half the patterns never happen

A filter that is its own undoing

The matrix that decides the spread

Two streams that look the same

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

shift register, 17 bits rank at size 24 ×17
the sampled yield at bias 0.2, depth 1, matches the recurrence ×12
the XOR of 1 flips is 1 with probability ½(1 − (1 − 2p)^k) ×12
and output 4, which was not ×11
xorshift, 32 bits rank at size 40 ×10
bit 0 of the state repeats every 2ᵏ⁺¹ steps ×8
all 4 windows of 2 bits occur somewhere in the period ×7
at 2 digits the middle square lasts a fraction of a random map's run ×4
seed 6239 repeats after the step the census says ×4
the recovered rule matches output 0, which was given ×4
the modulus is a whole number between 16 and 65536 ×3
the register of 4 bits visits every nonzero state before repeating ×3
xorshift128+, lowest bit rank at size 144 ×2
a coin that can land either way ×1
a multiplier consistent with the outputs exists ×1
a multiplier is a whole number between 2 and 1048576 ×1
a short vector the modulus annihilates exists ×1
an even number of flips drawn, so they pair up ×1
and arrives at p(1 − p) bits per flip ×1
and it is a de Bruijn sequence: every window of that width, exactly once ×1
and its neighbouring output bits are correlated ×1
and never exceed the Chor–Goldreich bound ×1
and so is the second ×1
and the all-zero window never appears ×1
and the outputs cover as many values as random draws would ×1
and the plain generator's ×1
and they occur equally often, but for the one the all-zero state would have supplied ×1
and visits every sixteen-bit state once ×1
and visits none of them twice ×1
applying the filter twice returns the word ×1
below its state size the generator gives nearly full rank ×1
between 32 and 256 steps ×1
bit b of the high byte is state bit b + 8, repeating every 2ᵇ⁺⁹ steps ×1
bits above the lowest few are nonlinear and give nearly full rank ×1
each extra level adds, and none passes the entropy ×1
each of them exactly once ×1
each output bit is the sum of the bits five and two places before it ×1
each window is between one bit and the register's width ×1
every generator's points fall on a genuine family of parallel lines ×1
every output bit of the permuted generator has the full period ×1
every point of the sequence satisfies the relation exactly ×1
every random rectangle obeys Lindsey's bound ×1
every seed ends in exactly one cycle ×1
four outputs pin the permuted generator's state down to one ×1
how many high bits are predicted is a whole number between 1 and 8 ×1
Lindsey's lemma: the rectangle's sum is at most √(|A||B|N) ×1
middle-square seeds repeat in less than half the steps a random map's would ×1
no filter passes the ceiling ×1
no four-digit cycle is longer than four ×1
no matrix from a linear generator exceeds the state size in rank ×1
no more rows than state bits ×1
no short whole-number relation holds between consecutive outputs ×1
on the two perpendicular sets every entry is the same ×1
only the 32-bit linear generator fails at forty ×1
rank of the 192 × 192 grid from xorshift128+'s lowest bit ×1
rank of the 48 × 48 matrix from the 32-bit xorshift ×1
rank of the nine-by-nine grid from a five-bit register ×1
raw, beyond one bit, only three outputs in a row are evenly spread — the three words of state ×1
raw, the patterns that occur number 2^rank ×1
six digits: seventeen cycles, the longest of 210 ×1
sources on coordinate blocks give bias ½·2^−(overlap) ×1
tempered the rows are independent and raw they are not ×1
tempered, every pattern occurs equally often but zero, which is one short ×1
tempered, likewise ×1
tempered, the rank is full ×1
tempering never makes the spread worse at any depth ×1
the all-zero state is the one the register cannot leave ×1
the all-zero window is the one that is short, by exactly one ×1
the bare rule from this seed visits only a handful of values ×1
the criterion and the measured period agree ×1
the dimension is a whole number between 2 and 3 ×1
the drawn steps compute the generator's output ×1
the example word is a whole number between 0 and 255 ×1
the filter sends the 256 words to 256 different words ×1
the first prime is a whole number between 3 and 4000 ×1
the first prime is three modulo four, which the construction requires ×1
the first seed is one of the longest-lived ×1
the flips drawn is a whole number between 8 and 48 ×1
the high byte's triples fail it by far ×1
the highest tap is the register's own width, or it is a shorter register ×1
the increment is a whole number between 0 and 1048576 ×1
the inner product is closer to fair than either simple rule ×1
the linear solve, run on this generator, predicts the next output wrongly ×1
the modulus is small enough that the arithmetic stays exact ×1
the multiplied generator gives a nearly full rank ×1
the multiplier is a whole number ×1
the multiplier is a whole number between 2 and 1048576 ×1
the multipliers really do differ, by more than a factor of two in spacing ×1
the multiplying generator passes the rank test at 32 ×1
the number of outputs it then predicts is a whole number between 2 and 16 ×1
the number of outputs the solver is given is a whole number between 3 and 8 ×1
the number of points is a whole number between 16 and 4096 ×1
the number of predictions is a whole number between 50 and 4000 ×1
the number of triples is a whole number between 100 and 4000 ×1
the occupied hyperplanes are consecutive, so the family has no gaps ×1
the output is balanced to within sampling error ×1
the output of the sticky source is balanced ×1
the output shows every nonzero window of the register's width ×1
the outputs drawn is a whole number between 16 and 96 ×1
the patched sequence is as long as there are windows ×1
the pattern is eight bits, so it fits a 16 × 16 grid ×1
the permuted output leaves the share of empty cells a random sequence would ×1
the permuted output's triples pass the chi-squared test ×1
the predictor gets essentially every output right ×1
the rectangle is one of random, subspace ×1
the register does not repeat before its full period ×1
the register visits every non-zero state before repeating ×1
the register width is a whole number between 5 and 14 ×1
the relation involves the middle coordinate, so an edge-on view exists ×1
the relation involves the second coordinate ×1
the relation's normal lies in the screen, so the planes are seen edge on ×1
the second prime is a whole number between 3 and 4000 ×1
the solver is given only a handful of outputs ×1
the state is a sixteen-bit number ×1
the state returns to its start after exactly 2¹⁶ steps ×1
the state's own bytes leave far more empty ×1
the taps are positions inside the register ×1
the triples lie on a small number of planes ×1
the twisted generator runs through every non-zero state before repeating ×1
the two multipliers give different numbers of lines ×1
the vector really does annihilate every point ×1
the view is one of compare, period, planes, lfsr, spectral, recover, nextbit, bbs, equi, vneumann, rates, sticky, xor, kdist, patterns, rankgrid, temper, raster, twosourcegrid, lindsey, twosourcebias, twosourcesim, pcgbits, pcgpairs, pcgmachine, pcgtriples, pcgrecover, pcgperiods, mswalks, mstails, mscycles, msscale, msweyl ×1
the width of the register is a whole number between 3 and 6 ×1
three to eight multiplier-and-increment pairs ×1
three to six bits ×1
two multipliers below the modulus ×1
two taps ×1
which is enormously better than guessing the leading bits ×1
while the independent coin's output shows no correlation ×1
with the counter, no state repeats in the run ×1

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Computation

A filter that changes only the spread

The generator most simulations use passes every output through a last scrambling step before anyone sees it. The step is reversible, it changes nothing about the period, and it cannot make the generator any less predictable. What it changes is which patterns of consecutive outputs can occur at all — on a small twisted generator, from half of them to every one.

Computation

A grid of bits whose rank stops at the state

Fill a square grid with a generator's output bits and compute its rank over the field of two elements. Random bits give full rank or one short, in fixed proportions. A generator built from shifts and exclusive-ors gives full rank up to its number of state bits and then never one more — 32 for a 32-bit xorshift, 128 for the lowest bit of xorshift128+ — however large the grid. The test that catches it is decided by a line of linear algebra.

Computation

A memory of four bits

A register holding four bits, shifting them along and adding two of them back, runs through all fifteen nonzero states before it repeats. Which two are added back is a question about a polynomial, and getting it wrong costs fourteen of the fifteen.

Computation

A page that knows where it is

A four-by-four array of bits, cyclic in both directions, in which every two-by-two block appears exactly once. Print it repeatedly across a sheet and any four marks on that sheet are an address.

Computation

A rotation that hides the lattice

A congruential generator modulo a power of two has a lowest bit that alternates and pairs of outputs that lie on a few lines. Keep the generator exactly as it is, and show only eight bits of each state, rotated by an amount the state's own top bits choose: every output bit now runs the full cycle, the pairs fill the square as a random sequence would, and triples pass a test the state's own bits fail by a factor of six. Nothing about the state has changed, and four outputs still give it away.

Computation

Fair bits from an unfair coin

Read a biased coin's flips in pairs, keep 01 as 0 and 10 as 1, and throw away the rest: the output is exactly fair, whatever the bias, and nobody needs to know the bias. The trick wastes most of the coin, the waste can be recycled almost up to the ceiling Shannon's entropy sets — and it fails quietly the moment the flips remember each other.

Computation

Four numbers and the rule is yours

A linear generator can be solved. Given a few of its outputs, the multiplier and the increment fall out of two congruences, and every future output is then known exactly — which is a failure of a completely different kind from the lattice defect, and is not detected by any test of how evenly the points are spread.

Computation

Nineteen thousand bits of state

The generator most simulations actually use is not clever. It is a linear recurrence over the two-element field with an enormous state, and its virtues are a proved period, a proved equidistribution and speed — none of which is unpredictability, which it does not have and does not claim.

Probability

Points too even to be random

Independent random points clump, and the clumping is what makes the error fall only as the square root. Points chosen to be evenly spread rather than independently beat that rate, and the price is that nothing about them is random at all.

Computation

Randomness that has to be earned

A generator that resists prediction cannot be built out of a rule anybody can fit. It has to be built out of a computation believed hard to undo, and the belief is the load-bearing part — which makes cryptographic randomness a conditional statement rather than a construction.

Computation

Square it and keep the middle

John von Neumann's first generator of random numbers squared a number and kept its middle digits. Followed from every four-digit seed, it never lasts more than 111 steps before a value repeats — a third of what the birthday problem allows a truly random rule — and one seed in five ends at zero for ever. A counter added before each squaring cures the collapse.

Computation

The planes a recurrence cannot leave

One multiplication and one addition, taken modulo a fixed number, produce a sequence that passes for random one value at a time. Taken two or three at a time it does not, and the reason is a whole-number relation that pins every point onto one of a small family of parallel lines.

Computation

The test that ranks the generators

Every linear generator's output lies on a family of parallel planes. Which generator is better is decided by how far apart those planes are, and that distance is the length of the shortest whole-number vector the modulus annihilates — a quantity that can be computed exactly rather than estimated by testing.

Computation

Two weak sources make one fair bit

No fixed rule can turn every weakly random source into fair bits: for any rule, some source with almost full unpredictability makes it constant. Two independent sources are different. Multiply their bits in pairs, add, and keep the parity — and if the two together carry more unpredictability than the length of one, the result is nearly fair, whatever else the sources do. The reason is that the table of those parities is balanced on every large rectangle.

The whole library · What the figures prove