Concept

Period

How many steps a repeating sequence takes before it comes back to where it started. For a generator it bounds how much output is usable, and for a linear recurrence over a finite field it is decided by whether a polynomial is primitive.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

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.

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 · Pseudorandomness

Every pattern, exactly as often. A table over 4 window lengths of a shift register's output stream: how many bit patterns are possible, how many actually occur, and the difference between the most and least frequent, which is one in every row.

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.

computation · Pseudorandomness

Named alongside it

The objects these essays reach for when they reach for this one.

Counting argument Divisibility Equidistribution Exhaustive search Finite field Hyperplane Lattice Linear recurrence Modular arithmetic Operation set Polynomial Primes

All concepts