Concept

Linear recurrence

A rule that gives each term of a sequence as a fixed weighted sum of the terms just before it. Its solutions are sums of powers of the roots of one polynomial, which is why such sequences grow geometrically and can be computed quickly by repeated squaring of a matrix.

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

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

How far a filter spreads a generator's output. Bars for bit depths 1 to 8: the ceiling ⌊24/v⌋ outlined, the raw generator's count of evenly spread consecutive outputs (24, 3, 3, 3, 3, 3, 3, 3), and the tempered count (24, 12, 6, 6, 3, 3, 3, 3).

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

Named alongside it

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

Equidistribution Finite field Period Pseudorandomness Basis Involution Pigeonhole principle Polynomial Primes Randomness Rank

All concepts