Random numbers are vital ingredients in many applications. From cryptography to lottery games, the source of unpredictable values generally comes from either a pseudo-random generator which relies upon algorithms on a computing device or a physical random generator that measures some physical observable expected to behave randomly [9]. The scope of the latter is beyond the capabilities of a Nintendo Entertainment System (NES) with a 6502 processor, so this page will concentrate on the former.

As laid out by Marsaglia, George, Arif Zaman, and Wai Wan Tsang, a list of desirable properties for a random number generator might include:

• Randomness. Provides a sequence of independent uniform random variables suitable for all reasonable applications. In particular, passes all the latest tests for randomness and independence.
• Long Period. Able to produce, without repeating the initial sequence, all the random variables for the huge samples that current computer speeds make possible.
• Efficiency. Execution is rapid, with modest memory requirements.
• Repeatability. Initial conditions (seed values) completely determine the resulting sequence of random variables.
• Portability. Identical sequences of random variables may be produced in a wide variety of computers, for given starting values.
• Homogeneity. All subsets of bits of the numbers must be random, from the most- to the least-significant bits.

[10]

We seek a generator in a games console that has many of these properties, although the context of the game dictates whether the completeness of a long period, or whether the latest tests must be satisfied. For instance, a NES game player may not be trivialised as much by a non-truly random damage output of an enemy's weapon considering the vast expense such legitimacy would require.

The use case can also impact the choice of generator. With binary representations, care should be taken if only inspecting a single bit as binary sequences produced by Grogono's generator, Turbo Pascal, or Unix's rand, have been shown to exhibit small period cycling in it's least significant bits [11].

On a deterministic computer [1] such as the NES, deterministic meaning that, at most, only one state can follow another during computation[2], A truly random number generator (RNG) in such a system can be hard as there are no other states that can occur, thus true randomness is not achievable. However, despite the deterministic nature of the NES a pseudo-random number generator (PRNG) can be used [3], which allows for the numbers to be selected which have seemingly no discernible pattern. In the case of the NES or more specifically the 6502 a linear-feedback shift register (LFSR) is one such example of how you could create a PRNG.

Once such method is visible in this code snippet[4]:

LDA seed
ASL A
ASL A
CLC
ADC seed
CLC
ADC #03
STA seed

"What this essentially does is multiply a seed value by 5, then add some other number (in this case, 3). As long as the last number added is prime, it will cycle through all 256 possible values before repeating (including 0, unlike an LSFR). If you want even more randomness, you could have several different RNG subroutines set up that add different prime numbers to create different sequences for different things."[4]

This method utilises bit shifting to create a sequence of values that fill the register with every possible value (except 0) [3]. Similar to multiplication methods, the nature of binary bit shifting can be taken advantage of to generate new values in novel ways. In this shown case, the series of bits is either shifted left using ASL to add in a zero value to the bit 0, or rotated using the ROL instruction. The latter uses the carry flag to store and rotate the shifted in bit with the previous shifted out bit. The shift is not immediate as the contents of the carry flag act as an additional step between the values moving [5]. This only increases the illusion of randomness, giving a sequence of 65535 numbers before repeating [3] calculated as 2^kv - 1, or 2^{(2 * 8)} - 1 as the trivial upper bound [8].

prng:
    LDX #8      ; Iteration count (generates 8 bits)
    LDA seed+0  ; Load the seed value into the accumulator (A) register
prng_1:
    ASL A       ; Bit shift the A register left, also acts as a multiply by 2, 
                ; Bit 0 is set to 0 and bit 7 is placed into the carry flag [6]
    ROL seed+1  ; Rotates the bit shift left. Similar to ASL except bit 0 is
                ; set to the current value of the carry flag [5]
    BCC prng_2  ; If the carry flag is clear, branch to prng_2, skipping the EOR
    EOR #$2D    ; apply XOR feedback whenever a 1 bit is shifted out
prng_2:
    DEX         ; Decrement the X register (8 bit iteration count) 
    BNE prng_1  ; If the decrement has not set the zero flag (X!=0) then branch
                ; back to prng_1 for another iteration
    STA seed+0  ; Else once all iterations are complete, store the contents of
                ; the A register as a new seed
    CMP #0      ; Finally reload all of the flags
    RTS

[7] adapted from [3]

The contributors of [13] recommend using the method described in [3] for the actual number generation part. In particular, they recommend the algorithm found in [14]. Many of the contributors of [13] go beyond the advice found in [3] describing a way to provide a seemingly random seed to then be used in the algorithm found in [14] which implements Linear feedback shift register. To get this seed the contributors of [13] recommend having a frame counter on the title screen. This counter will stop counting when the player presses start. This counter will then act as the seed.

[1] https://en.wikipedia.org/wiki/Deterministic_system

[2] https://www.quora.com/What-is-the-meaning-of-deterministic-and-non-deterministic-in-computer-science

[3] https://wiki.nesdev.com/w/index.php/Random_number_generator

[4] http://www.gravelstudios.com/dabadace/post.php?postid=27

[5] Andrew John Jacobs - ROL instruction reference

[5] Andrew John Jacobs - ASL instruction reference

[7] Associate Professor Edward Powley - YouTube live coding sessions, video 8, 18:00

[8] Matsumoto, Makoto, and Takuji Nishimura. "Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator." ACM Transactions on Modeling and Computer Simulation (TOMACS) 8.1 (1998): 3-30

[9] Jennewein, Thomas, et al. "A fast and compact quantum random number generator." Review of Scientific Instruments 71.4 (2000): 1675-1680

[10] Marsaglia, George, Arif Zaman, and Wai Wan Tsang. "Toward a universal random number generator." Stat. Prob. Lett. 9.1 (1990): 35-39

[11] Park, Stephen K., and Keith W. Miller. "Random number generators: good ones are hard to find." Communications of the ACM 31.10 (1988): 1192-1201

[13] http://forums.nesdev.com/viewtopic.php?t=6757

[14] http://codebase64.org/doku.php?id=base:small_fast_8-bit_prng