Random number generator: Difference between revisions

From NESdev Wiki
Jump to navigationJump to search
(→‎External references: should probably directly link CC65's rand since it's a good'un)
m (→‎External references: typo: 32 vs 23?)
Line 52: Line 52:


== External references ==
== External references ==
* [https://github.com/cc65/cc65/blob/master/libsrc/common/rand.s CC65's rand.s] (a good quality 23-bit LCG, [http://forums.nesdev.org/viewtopic.php?f=2&t=14499 forum commentary])
* [https://github.com/cc65/cc65/blob/master/libsrc/common/rand.s CC65's rand.s] (a good quality 32-bit LCG, [http://forums.nesdev.org/viewtopic.php?f=2&t=14499 forum commentary])
* nesdev forum: [http://forums.nesdev.org/viewtopic.php?f=2&t=13172 Which randomizer to use?]
* nesdev forum: [http://forums.nesdev.org/viewtopic.php?f=2&t=13172 Which randomizer to use?]
* nesdev forum: [http://forums.nesdev.org/viewtopic.php?f=10&t=11241 need assistance with random number generator]
* nesdev forum: [http://forums.nesdev.org/viewtopic.php?f=10&t=11241 need assistance with random number generator]
* nesdev forum: [http://forums.nesdev.org/viewtopic.php?f=2&t=9598 CRC routines as PRNGs]
* nesdev forum: [http://forums.nesdev.org/viewtopic.php?f=2&t=9598 CRC routines as PRNGs]
* [http://codebase64.org/doku.php?id=base:6502_6510_maths#random_numbers Codebase64.org PRNG code examples]
* [http://codebase64.org/doku.php?id=base:6502_6510_maths#random_numbers Codebase64.org PRNG code examples]

Revision as of 00:05, 13 August 2018

While truly random numbers are difficult to create with a deterministic computer, a pseudorandom number generator, or PRNG, may be used instead, which is technically deterministic, but designed so that the output should appear consistently uncorrelated. There are a wide variety of suitable algorithms.

Typically a starting "seed" is supplied by the program to begin the sequence generated by a PRNG. By finding some way[1] of gathering a suitably unpredictable starting seed, (e.g. counting the time until the user presses a button) the program can start at a different part of the sequence each time it is run, ensuring the user does not have the same experience twice.

Linear feedback shift register

The linear feedback shift register is commonly used as a PRNG on systems like the 6502 which have no hardware multiply capabilities. This rotates a series of bits (the shift register), with the bit coming off the end of the series feeding back into the register as an exclusive-OR operation. By choosing the feedback bits carefully, this can create a sequence that fills the register with every possible value (except 0), allowing relatively long random number sequences using only bitwise operations.

This example is only 16 bits wide, but the sequence length of an LSFR can be doubled with each bit. 24 and 32 bit LSFRs are very practical if extremely long sequences are needed.

; prng
;
; Returns a random 8-bit number in A (0-255), clobbers X (0).
;
; Requires a 2-byte value on the zero page called "seed".
; Initialize seed to any value except 0 before the first call to prng.
; (A seed value of 0 will cause prng to always return 0.)
;
; This is a 16-bit Galois linear feedback shift register with polynomial $002D.
; The sequence of numbers it generates will repeat after 65535 calls.
;
; Execution time is an average of 125 cycles (excluding jsr and rts)

.zeropage
seed: .res 2       ; initialize 16-bit seed to any value except 0

.code
prng:
	ldx #8     ; iteration count (generates 8 bits)
	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

See Linear feedback shift register (advanced) for further commentary on this code, and various alternatives with other desired properties (efficiency, quality, etc.).

See also

References

External references