Random number generator: Difference between revisions

From NESdev Wiki
Jump to navigationJump to search
m (clarify further the role of prng_xbits)
m (→‎Linear feedback shift register: make it clearer where the prng_6502 link is going)
 
(13 intermediate revisions by 3 users not shown)
Line 1: Line 1:
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.
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<ref>[http://forums.nesdev.org/viewtopic.php?f=2&t=9796 Forum discussion of obscure methods of gathering seed entropy.]</ref> 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.
Typically a starting "seed" is supplied by the program to begin the sequence generated by a PRNG. By finding some way<ref>[//forums.nesdev.org/viewtopic.php?p=107596#p107596 Forum discussion of obscure methods of gathering seed entropy.]</ref> 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 ==
== Linear feedback shift register ==
Line 7: Line 7:
The [https://en.wikipedia.org/wiki/Linear_feedback_shift_register 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.
The [https://en.wikipedia.org/wiki/Linear_feedback_shift_register 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.
This example<ref>[https://github.com/bbbradsmith/prng_6502 prng_6502: a Galois LSFR RNG]</ref> is only 16 bits wide, but the sequence length of an LSFR can be doubled with each additional bit.
 
If you need to generate large batches of random numbers at once, a [[Random number generator/Linear feedback shift register (advanced)#Overlapped_24_and_32_bit_LFSR|24 or 32-bit LFSR]] is recommended. Wider LFSRs are still very practical, and produce extremely long random number sequences. Narrower LFSRs are also possible, but not generally recommended due to their short, repetitive sequences.
 
See [[Random number generator/Linear feedback shift register (advanced)|Linear feedback shift register (advanced)]] for further commentary on this code, and various alternatives with other LFSR widths and properties (efficiency, quality, etc.).
 
=== Simple ===


<pre>
<pre>
; prng
; prng
;
;
; Returns a random 8-bit number in A (0-255), clobbers X (0).
; Returns a random 8-bit number in A (0-255), clobbers Y (0).
;
;
; Requires a 2-byte value on the zero page called "seed".
; Requires a 2-byte value on the zero page called "seed".
Line 18: Line 24:
; (A seed value of 0 will cause prng to always return 0.)
; (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.
; This is a 16-bit Galois linear feedback shift register with polynomial $0039.
; The sequence of numbers it generates will repeat after 65535 calls.
; The sequence of numbers it generates will repeat after 65535 calls.
;
; The value loaded in X controls the quality of randomness.  Each iteration
; produces another random bit.  All 8 bits will produce maximum entropy,
; but this value can be lowered to increase speed if you need only low-order
; bits.  If using the same value each time (prng), use 8, 7, 4, 2, 1.
; Avoid long runs of 6, 5 and 3, as they shorten the sequence by having
; common factors with 65535.  If you use different amounts of low-order bits
; each time, such as random numbers in different ranges in different parts
; of a game, you can use prng_xbits to change how many bits are produced
; followed by an AND to drop unused bits.
;
;
;
; Execution time is an average of 125 cycles (excluding jsr and rts)
; Execution time is an average of 125 cycles (excluding jsr and rts)
Line 39: Line 34:
.code
.code
prng:
prng:
ldx #8    ; iteration count: controls entropy quality (max 8,7,4,2,1 min)
ldy #8    ; iteration count (generates 8 bits)
prng_xbits:
lda seed+0
lda seed+0
@bitloop:
:
asl        ; shift the register
asl        ; shift the register
rol seed+1
rol seed+1
bcc :+
bcc :+
eor #$2D   ; apply XOR feedback whenever a 1 bit is shifted out
eor #$39   ; apply XOR feedback whenever a 1 bit is shifted out
:
:
dex
dey
bne @bitloop
bne :--
sta seed+0
sta seed+0
cmp #0    ; reload flags
cmp #0    ; reload flags
rts
rts
</pre>
</pre>
19 bytes, 133-141 cycles per call (average 137).
=== Overlapped ===
This is equivalent to the simple version above, but performs 8 iterations at once in a complex overlapped operation.
<pre>
; Returns a random 8-bit number in A (0-255), clobbers Y (unknown).
prng:
lda seed+1
tay ; store copy of high byte
; compute seed+1 ($39>>1 = %11100)
lsr ; shift to consume zeroes on left...
lsr
lsr
sta seed+1 ; now recreate the remaining bits in reverse order... %111
lsr
eor seed+1
lsr
eor seed+1
eor seed+0 ; recombine with original low byte
sta seed+1
; compute seed+0 ($39 = %111001)
tya ; original high byte
sta seed+0
asl
eor seed+0
asl
eor seed+0
asl
asl
asl
eor seed+0
sta seed+0
rts
</pre>
35 bytes, 69 cycles.
== See also ==
* [[Least recently used]]
* [[Random number generator/Linear feedback shift register (advanced)|Linear feedback shift register (advanced)]]


== References ==
== References ==
<references />
<references />
== External references ==
* [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=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]
* [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]
Past forum discussions of random number generators:
* Forum: [http://forums.nesdev.org/viewtopic.php?f=2&t=14499 Quality of the CC65 randomizer] (a 23-bit LCG)
* Forum: [http://forums.nesdev.org/viewtopic.php?f=2&t=13172 Which randomizer to use?]
* Forum: [http://forums.nesdev.org/viewtopic.php?f=10&t=11241 need assistance with random number generator]
* Forum: [http://forums.nesdev.org/viewtopic.php?f=2&t=9598 CRC routines as PRNGs]

Latest revision as of 17:03, 20 February 2021

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[2] is only 16 bits wide, but the sequence length of an LSFR can be doubled with each additional bit.

If you need to generate large batches of random numbers at once, a 24 or 32-bit LFSR is recommended. Wider LFSRs are still very practical, and produce extremely long random number sequences. Narrower LFSRs are also possible, but not generally recommended due to their short, repetitive sequences.

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

Simple

; prng
;
; Returns a random 8-bit number in A (0-255), clobbers Y (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 $0039.
; 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:
	ldy #8     ; iteration count (generates 8 bits)
	lda seed+0
:
	asl        ; shift the register
	rol seed+1
	bcc :+
	eor #$39   ; apply XOR feedback whenever a 1 bit is shifted out
:
	dey
	bne :--
	sta seed+0
	cmp #0     ; reload flags
	rts

19 bytes, 133-141 cycles per call (average 137).

Overlapped

This is equivalent to the simple version above, but performs 8 iterations at once in a complex overlapped operation. 

; Returns a random 8-bit number in A (0-255), clobbers Y (unknown).
prng:
	lda seed+1
	tay ; store copy of high byte
	; compute seed+1 ($39>>1 = %11100)
	lsr ; shift to consume zeroes on left...
	lsr
	lsr
	sta seed+1 ; now recreate the remaining bits in reverse order... %111
	lsr
	eor seed+1
	lsr
	eor seed+1
	eor seed+0 ; recombine with original low byte
	sta seed+1
	; compute seed+0 ($39 = %111001)
	tya ; original high byte
	sta seed+0
	asl
	eor seed+0
	asl
	eor seed+0
	asl
	asl
	asl
	eor seed+0
	sta seed+0
	rts

35 bytes, 69 cycles.

See also

References

  1. ↑ Forum discussion of obscure methods of gathering seed entropy.
  2. ↑ prng_6502: a Galois LSFR RNG

External references

Retrieved from "https://www.nesdev.org/w/index.php?title=Random_number_generator&oldid=11006"