THE LFSR a few taps and a shift — 15 pseudo-random states from four bits
A linear-feedback shift register makes a long stream of pseudo-random bits from almost nothing: shift the register left, and feed back the XOR of a few chosen tap positions into the empty bit. With the right taps (a primitive polynomial), a 4-bit register cycles through all 15 nonzero states before repeating — the maximum possible. LFSRs are everywhere hardware needs cheap randomness or a spread: stream ciphers, CRCs, test patterns, GPS codes. They are fast and tiny, and dangerously predictable alone — but they are the workhorse pseudo-random primitive.
THE TECHNIQUE shift + XOR of taps; primitive poly ⇒ period 2ⁿ−1
The demo runs a 4-bit LFSR (taps 4,3) from seed 1 and counts the cycle length — it visits all 15 nonzero states before returning: live demo
HISTORY & CREDIT LFSR · primitive polynomials (Golomb)
“Randomness needs entropy.” — pseudo-randomness needs only a shift and a couple of taps; the period is set by the polynomial. cited
the step · feedback = XOR of tap bits; shift left; drop the fed-back bit in at the bottom. the period · a primitive tap polynomial visits all 2ⁿ−1 nonzero states — maximal length. the uses · stream ciphers, CRC hardware, BIST test patterns, GPS Gold codes — Golomb’s shift-register theory.
A maximal cycle of pseudo-random states from a shift and two taps — cheap sequence, set entirely by the polynomial. generator
RECOMMEND FOR I-13 the maximal cycle, on the compiler
On the canonical compiler, the 4-bit LFSR from seed 1 returns to its start after exactly 15 steps — every nonzero state visited:
$ i13 run zd_lfsr.i13 # 4-bit LFSR, taps 4,3
RUN OK · 600 step(s) · peak stack 5 · call depth 16
seed = 1
per = 15 -- all 2^4 - 1 nonzero states, then repeat
Recommend as a NULL — a generator, hence resource. The LFSR produces a pseudo-random stream cheaply; its output is a fully determined sequence (given seed and taps), and the “win” is that it is small and fast. That is the resource family (B40): a deterministic function computed by a lean mechanism. The maximal period is a theorem about primitive polynomials (B39). NULL — the batch’s cheap-randomness workhorse.