Generator

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

A generator in the computation library, called 36 times across 8 essays. Below: what it draws at its defaults 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.

At its defaults

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.

`show: "lfsr"`

A 4-bit register that visits all 15 nonzero states. The first 15 states of a 4-bit linear feedback shift register with taps at 4 and 1, with the bit that leaves the register at each step; the output shows every nonzero window of 4 bits exactly once.

`show: "period"`

Which generators visit all 16 values. A table of multipliers and increments with the three conditions that decide whether the generator has the full period, beside the period found by running it out.

`show: "planes"`

1500 triples from a generator, on 15 planes. Consecutive triples of outputs of a linear congruential generator plotted in a cube, seen from an angle that shows them lying on a small number of parallel planes.

`show: "recover"`

Four outputs are enough to find the rule. A row of 12 outputs of a linear generator, with the first 4 marked as given and the rest as predicted. The multiplier and increment recovered from the given ones reproduce every later output exactly.

`show: "nextbit"`

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.

and output 4, which was not ×11
all 4 windows of 2 bits occur somewhere in the period ×7
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
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
and it is a de Bruijn sequence: every window of that width, exactly once ×1
and so is the second ×1
and the all-zero window never appears ×1
and they occur equally often, but for the one the all-zero state would have supplied ×1
and visits none of them twice ×1
each of them exactly once ×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 point of the sequence satisfies the relation exactly ×1
how many high bits are predicted is a whole number between 1 and 8 ×1
no short whole-number relation holds between consecutive outputs ×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 criterion and the measured period agree ×1
the dimension is a whole number between 2 and 3 ×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 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 linear solve, run on this generator, predicts the next output wrongly ×1
the modulus is small enough that the arithmetic stays exact ×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 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 shows every nonzero window of the register's width ×1
the patched sequence is as long as there are windows ×1
the predictor gets essentially every output right ×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 taps are positions inside the register ×1
the triples lie on a small number of planes ×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 ×1
the width of the register is a whole number between 3 and 6 ×1
three to eight multiplier-and-increment pairs ×1
two multipliers below the modulus ×1
two taps ×1
which is enormously better than guessing the leading bits ×1

Where it is called

Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.

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

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

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.

The whole library · What the figures prove