Random number generator/Linear feedback shift register (advanced)

From Nesdev wiki
Revision as of 11:19, 11 July 2016 by Rainwarrior (Talk | contribs) (Created page as a place for more advanced commentary on the LFSR example.)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Further commentary on the linear feedback shift register example at random number generator.

Basic version

prng:
	ldx #8     ; iteration count
	lda seed+0
:
	asl        ; shift the register
	rol seed+1
	bcc :+
	eor #$2D   ; apply XOR feedback whenever a 1 bit is shifted out
:
	dex
	bne :--
	sta seed+0
	cmp #0     ; reload flags
	rts

Sacrifice entropy for speed

The iteration count stored in X can be reduced to speed up the generator, at the expense of quality of randomness. Each iteration effectively generators one more bit of entropy, so 8 iterations are needed for an 8-bit random number. If you intend to use fewer bits of the result (e.g. use AND to mask the result), or if you are satisfied with less randomness, you can reduce X, or even parameterize it:

; X as a parameter specifies number of random bits to generate (1 to 8)
prng:
	lda seed+0
@bitloop:
	asl
	rol seed+1
	bcc :+
	eor #$2D
:
	dex
	bne @bitloop
	sta seed+0
	cmp #0
	rts

Alternatively this loop could be unrolled with 8 entry points, saving the need to use X or load it as a parameter.

Because the 16-bit LFSR has a repeating cycle of 65535 values, groups of 6, 5, or 3 bits will reduce the length of its output sequence. This should be avoided, if possible.

24 and 32 bit LFSR

TODO