Random number generator: Difference between revisions
Rainwarrior (talk | contribs) (revising entropy discussion link to start at Blargg's post that actually summarizes entropy gathering methods, the OP was an *incredibly* obtuse place to start) |
Rainwarrior (talk | contribs) (→Linear feedback shift register: adding more efficient but complex version) |
||
| 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 6502 Galois LSFR RNG]</ref> 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. | ||
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 | ; 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 28: | Line 32: | ||
.code | .code | ||
prng: | prng: | ||
ldy #8 ; iteration count (generates 8 bits) | |||
lda seed+0 | lda seed+0 | ||
: | : | ||
| Line 34: | Line 38: | ||
rol seed+1 | rol seed+1 | ||
bcc :+ | bcc :+ | ||
eor #$ | eor #$39 ; apply XOR feedback whenever a 1 bit is shifted out | ||
: | : | ||
dey | |||
bne :-- | bne :-- | ||
sta seed+0 | sta seed+0 | ||
| Line 43: | Line 47: | ||
</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 == | == See also == | ||
Revision as of 22:36, 27 September 2019
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 bit. 24 and 32 bit LSFRs are very practical if extremely long sequences are needed.
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 $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: 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
External references
- CC65's rand.s (a good quality 32-bit LCG, forum commentary)
- nesdev forum: Which randomizer to use?
- nesdev forum: need assistance with random number generator
- nesdev forum: CRC routines as PRNGs
- Codebase64.org PRNG code examples
