LFSR Random Numbers

Code status: illustrative pseudocode. Adapt the listing to your program and check it on your target machine. This page links no assembly or execution record for the listing itself.

Overview

A Linear Feedback Shift Register (LFSR) generates pseudo-random numbers by shifting bits and XORing feedback taps. The version below uses no multiplication and repeats the same sequence from the same seed. Its period and cost depend on the chosen width, feedback and implementation.

The 8-bit Galois LFSR shown here cycles through all 255 non-zero values before repeating — a small, inspectable sequence for some game choices, not a guarantee of good game design.

Algorithm

; 8-bit Galois LFSR with taps at bits 7, 5, 4, 3
; Polynomial: x^8 + x^6 + x^5 + x^4 + 1

random_seed: byte = $01    ; Must be non-zero!

get_random:
    load random_seed
    shift right            ; Carry = bit 0
    if carry set:
        xor #$B4           ; Feedback polynomial
    store random_seed
    return                 ; Result in accumulator

Pseudocode

; Initialise with any non-zero value
random_seed = $01

; Get next random number (1-255)
get_random:
    seed = random_seed
    carry = seed AND 1
    seed = seed >> 1
    if carry:
        seed = seed XOR $B4
    random_seed = seed
    return seed

; Get random in range 0 to max-1 (for powers of 2)
get_random_max(max):
    return get_random AND (max - 1)

; Example: random 0-15
direction = get_random AND $0F

Implementation Notes

6502:

get_random:
    lda random_seed
    lsr              ; Shift right, bit 0 -> carry
    bcc +            ; Skip XOR if carry clear
    eor #$B4         ; Apply feedback
+   sta random_seed
    rts

Z80:

get_random:
    ld a,(random_seed)
    srl a            ; Shift right, bit 0 -> carry
    jr nc,.no_xor
    xor $B4
.no_xor:
    ld (random_seed),a
    ret

68000:

get_random:
    moveq   #0,d0             ; define the whole return register
    move.b  random_seed,d0
    lsr.b   #1,d0
    bcc.s   .no_xor
    eor.b   #$B4,d0
.no_xor:
    move.b  d0,random_seed
    rts

Why the seed must never be zero

A Galois LFSR transitions to 0 only when fed 0 — the all-zero state has no 1 bit to shift out, so the carry is 0, no XOR happens, and the result stays 0 forever. Once the LFSR enters this trap it produces 0 every call.

Initialise this byte to a value from 1 to 255. If your seed value can come from external state (RAM contents, player input timing), test for zero and substitute 1:

; 6502: defensive seed
lda new_seed
bne .ok
lda #$01
.ok:
sta random_seed

An unexpected zero after valid initialisation is a fault to investigate: another routine may have cleared the seed. A diagnostic check can expose it. Substituting 1 for an external zero seed is an explicit input policy; silently doing that after corruption can hide the cause.

Trade-offs

When to use: Enemy spawn positions, random delays, shuffling, procedural generation.

When to avoid: Security-sensitive choices: this generator is predictable. Also avoid it when its short period or correlations harm the game. Mapping can produce zero, but the mapping needs its own distribution check.

A useful range is not automatically an even one

The raw sequence excludes zero, but value AND $0F can produce zero. Over a complete 255-value cycle, the masked result is zero 15 times and each value 1–15 appears 16 times. Masking reaches the intended range; it does not make these outcomes equally frequent. A short sample can vary further.

Before choosing a mapping, state the source range and the desired outcomes. For example, an ideal uniform byte from 0–255 mapped by remainder 6 gives four outcomes 43 source values each and two outcomes 42 each. Rejecting 252–255 before taking the remainder gives 42 source values per outcome, but requires another draw when rejected. That example assumes all 256 input values are equally likely; this non-zero LFSR is a different source.

Rejection also changes random-call counts and has a variable execution cost. An empty set of legal placements needs an explicit failure policy, not an unbounded “try again” loop. Equal counts do not establish independence or whether the resulting game is fair or enjoyable.

The same seed repeats this generator’s raw sequence only for the same algorithm and call order. A game also needs matching initial state, input/update timing and external values mixed into the generator. Adding a cosmetic random draw can change which later value becomes an enemy position. Log a call number and purpose when investigating a divergence; do not call the generator again just to print a diagnostic value.

Seeding

For variation between sessions, we can count observed update opportunities while waiting for Start. This illustrative loop depends on a machine-specific wait and a normalised input reader; it does not promise a different seed on every run:

; One increment per chosen update opportunity; keep an unsigned byte
seed_counter = 0
wait_for_start:
    wait_for_next_update()
    seed_counter = (seed_counter + 1) AND $FF
    start_pressed = read_start_button()
    if not start_pressed: goto wait_for_start
    random_seed = seed_counter
    if random_seed == 0: random_seed = 1  ; Never zero!

The counter wraps after 256 updates. The same observed delay can repeat a seed; zero is deliberately mapped to one. This provides variation, not security or an even distribution of starting states. For debugging, use a recorded non-zero seed and preserve random-call order instead.

Larger Periods

For 16-bit LFSR (65,535 values):

• Use polynomial $B400 (taps at 15, 13, 12, 10)
• Same algorithm, just with 16-bit operations

Verified native components

These components turn the byte algorithm above into reusable machine-specific code. Each has an include/init/call example, native execution evidence, customization and a completed wrong/fixed example. The shared illustrations remain explanations rather than interchangeable machine code.

• Seeded random numbers on C64
• Seeded random numbers on NES
• Seeded random numbers on ZX Spectrum
• Seeded random numbers on Amiga