Matpic
mathematics, in pictures
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 4 essays across 2 fields — 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 The powers of 4 roots, added: 1, −1, 4, −5. For k from 1 to 4, the k-th powers of the roots of a degree-4 polynomial drawn as arrows placed tip to tail. Each walk ends on the real axis at a whole number, the k-th power sum, which the coefficients determine.

Every power sum, from the coefficients alone

Raise the roots of a polynomial to the k-th power and add them. However the roots turn, the total is a whole number when the coefficients are, and Newton's identities produce it from the coefficients one step at a time — no root is ever found. Run the rule on x³ − x − 1 and out comes Perrin's sequence, whose terms know which numbers are prime, nearly.

algebra · Polynomial roots The low bits of a congruential generator, and the bits a permutation shows. First 128 steps of a 16-bit congruential generator: low state bits with periods 2, 4, 8, 16, 32, 64, 128, 256; permuted output bits all with period 65536.

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

Named alongside it

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

EquidistributionPeriodPseudorandomnessFinite fieldPolynomialBasisCoefficientComplex numbersExhaustive searchFermats little theoremInvolutionModular arithmetic

All concepts