Pseudo-Random Number generators

By Grim.

PRNGs (Pseudo-Random Number Generators) are deterministic algorithms that generate a finite sequence of numbers, completely determined by a small set of initial values called seeds, that looks like random as opposed to TRNGs (True Random Number Generators) which use an external source of entropy (that can not, hopefully, be predicted).

The quality of the sequence of numbers generated by a PRNG is measured on some of its statistical properties, such as:

  • Periodicity: The sequence generated by any PRNG will repeat at some point. The period of a PRNG is how many numbers it can produce before repeating. The longer it is, the better.
  • Equidistribution: A PRNG is said to be k-dimensionally equidistributed if the generated numbers are uniformly distributed in a k-dimensional cube through a whole period, that is, if every consecutive k numbers have no relation.
  • Serial Correlation: A sequence of random numbers should not have any correlation between successive numbers, meaning that you should not be able to predict the next number by looking at the previous ones.

Designing good PRNGs is hard and best left to dedicated professionals.

Totally Crap Number Generator

These “generators” shake and scramble register/memory values and spit out some new magical number. The most spectacular ones even use the R register because “it seems to be a good ideafamous last words

;;Input : Hope that HL, (HL), D and C will vary enough
;;Output: A = Crap Number
tcng8:
 ld a,r
 rlca
 xor (hl)
 xor d
 add c
 ret


Hard to know, for a normal human brain at least, what the output of that thing could be, so it must be good. No? Well … this is actually terrible. This sort of thing should be used very, very sparingly, or even better: only once.

When such routine is called regularly in a program, a very small set of input parameters (CPU registers and memory content) will emerge (because a program is basically a big pile of loops doing the same things, forever, especially in demo-programs), and as a result, you will get extremely poor randomness.

Linear Feedback Shift Register

LFSR-based PRNG algorithms use only shifts and XOR operations to generate a sequence of numbers, which usually make them fast and quite simple to implement (ie. all the appealing buzz-words crying for a Z80 implementation :)

Galois configuration

The routines presented here are based on the Flexible Galois LFSR algorithm, implemented with shift-left operation, which allows for shorter and faster implementation in Z80 assembly than the shift-right used in most online descriptions of the algorithm. LFSR only works if the seed value is not null (ie. not zero).

8-bit LFSR

;; 8-bit LFSR PRNG
;; Period: 255
;; Time: 13 / 14 µs (min/max)
;; Size: 11 bytes
;;
;; Output:
;;  A = Random number
;;  Flags are modified

lfsr8:
_lfsr8_var EQU $+1
           ld a,51 ; Seed
           add a,a
           jr nc,_lfsr8
             xor %00011101
_lfsr8     ld (_lfsr8_var),a
           ret

Crapified 8-bit LFSR

;; Crapified 8-bit LFSR PRNG
;; Period:
;;  Min: 255
;;  Max: 32640
;; Time: 16 / 17 µs (min/max)
;; Size: 
;;
;; Output:
;;  A = Random number
;;  C,Flags are modified

clfsr8:
_clfsr8_var EQU $+1
            ld a,51 ; Seed
            add a,a
            jr nc,_clfsr8
              xor %00011101
_clfsr8     ld (_clfsr8_var),a
            ; crapification
            ld c,a
            ld a,r
            add a,c
            ret

This will “improve” results a bit.


16-bit LFSR

;; 16-bit PRNG
;; Period : 65535
;; Time : 19 µs (constant)
;; Size: 13 bytes
;;
;; Output:
;;  HL = Random number
;;  A = L
;;  Flags are modified

lfsr16:
_lfsr16_var EQU $+1
            ld hl,&6128 ; Seed
            add hl,hl
            sbc a,a
            and &83
            xor l
            ld l,a
            ld (_lfsr16_var),hl
            ret

XorShift

Xorshift RNGs are a subclass of linear feedback shift registers that was discovered by George Marsaglia. They provide longer and significantly better sequences than LFSR PRNG, at the cost of execution speed.

Like Galois LFSR PRNG, the seeds must be initialized so that they are not all null (ie. anything but zeros). It is also recommended to initialize them with distinct values rather than a lazy “all zero but one“.

XorShift128

;; XorShift128 PRNG
;; Period: (2^128)-1
;; Time: 191 µs
;; Size: 103 bytes, including the 16-bytes (128-bit) seed buffer.
;;
;; Output:
;;  HLDE hold a 32-bit random number
;;  BC = 0
;;  AF,IX are modified

xorshift128:
     ;; DE = X.MSB
     ;; BC = X.LSB
     ;; AHL = EBC = X << 8
     ld de,(_xorshift128_var_x_msb)
     ld hl,(_xorshift128_var_x_lsb)
     ld a,e
     ld b,h
     ld c,l
     ;; AHL = AHL << 3
     add hl,hl
     rla
     add hl,hl
     rla
     add hl,hl
     rla
     ;; D = D ^ A
     xor d
     ld d,a
     ;; E = E ^ H
     ld a,e
     xor h
     ld e,a
     ;; B = B ^ L
     ld a,b
     xor l
     ld b,a
     ;; DEBC = X ^ (X << 11) = T
     ;; HL = W.MSB
     ;; IX = W.LSB
     ld hl,(_xorshift128_var_w_msb)
     ld ix,(_xorshift128_var_w_lsb)
     push hl
     ;; HL = HL >> 3 = W >> 19
     srl h
     rl l
     srl h
     rl l
     srl h
     rl l
     ;; C = C ^ B ^ L ^ IXl
     ld a,c
     xor b
     xor l
     xor ixl
     ld c,a
     ;; B = B ^ E ^ H ^ IXh
     ld a,b
     xor e
     xor h
     xor ixh
     ld b,a
     ;; HL = W.MSB
     pop hl
     ;; E = E ^ D ^ L
     ld a,e
     xor d
     xor l
     ld d,a
     ;; D = D ^ H
     ld a,d
     xor h
     ld d,a
     ;; DEBC = (T ^ (T >> 8)) ^ (W >> 19) ^ W = New W
     push de
     push bc
     ;; X <- Y <- Z <- W
     ld hl,_xorshift128_var_y
     ld de,_xorshift128_var_x_lsb
     ld bc,3*4
     ldir
     ;; W <- New W
     pop de
     ld (_xorshift128_var_w_lsb),de
     pop hl
     ld (_xorshift128_var_w_msb),hl
     ;; HLDE = New 32-bit random number
     ;; BC = 0
     ;; A = H
     ret

;; 16 bytes seed buffer
_xorshift128_var_x_lsb  DB &01,&02
_xorshift128_var_x_msb  DB &03,&04
_xorshift128_var_y      DB &05,&06,&07,&08
_xorshift128_var_z      DB &09,&0a,&0b,&0c
_xorshift128_var_w_lsb  DB &0d,&0e
_xorshift128_var_w_msb  DB &0f,&10

XorShift variants

If the heavy-weight 128-bits implementation above is too big/slow for your liking, here are some down-sized variants (smaller seed-buffer, 96 down to 32-bit only) you can implement.

32-bit

  • Single 32-bit seed : X
  • Algorithm
    • X ^= X<<13
    • X ^= X>>17
    • X ^= X<<15
    • New 32-bit random number in X

64-bit

  • Two 32-bit seeds : X and Y
  • Algorithm
    • T = X^(X<<10)
    • X = Y
    • Y = (Y^(Y>>10))^(T^(T>>13))
    • New 32-bit random number in Y

96-bit

  • Three 32-bit seeds : X, Y and Z
  • Algorithm
    • T = (X^(X<<10))
    • X = Y
    • Y = Z
    • Z = (Z^(Z>>26))^(T^(T>>5))
    • New 32-bit random number in Z

Complementary-multiply-with-carry generators

Complementary Multiply with carry is a method invented by George Marsaglia (again). It generates a sequence of random integers based on an initial set of seed values.

x_n=(b-1)-(ax_{n-r}+c_{n-1}),bmod,b, c_n=leftlfloorfrac{ax_{n-r}+c_{n-1}}{b}rightrfloor.

Quality wise, it’s rock solid. Period can be astonishingly huge. And it’s quite fast. The following implementation of the algorithm was tuned to quickly generate 8-bit integers from only 8 seeds (to keep the memory usage small).

I highly recommend using this PRNG by default and, only if it does not fit your purpose, try out XorShift or LFSR.

8-bit CMWC

  • Prime multiplier : a = 253
  • Base : b = 256
  • A set of 8 seeds, r = 8

The 8-bytes seed buffer in the following implementation must not cross a 256-byte address boundary.

;; 8-bit CMWC PRNG
;; Period: ~2^66
;; Time: 46µs
;; Size: 43 bytes, including the 8-bytes seed buffer.
;;
;; Note:
;;  The seed buffer must not cross a 256-byte address boundary
;;
;; Output
;;  A = 8-bit random number
;;  Flags,HL,DE,BC are modified

cmwc8:
            ; Init (i,c)
_cmwc8_var  EQU $+1
            ld bc,0
            ; Read q[i]
            ld hl,_cmwc8_seed
            ld a,b
            add a,l
            ld l,a
            ld d,(hl) ; D = y = q[i]
            ; Compute 253*y + c
            ld e,d      ; E = y
            ld a,c      ; A = c
            sub e       ; A-= y
            jr nc,$+3
              dec d
            sub e       ; A-= y
            jr nc,$+3
              dec d
            sub e       ; A-= y
            jr nc,$+3
              dec d
            ; DA = 256*y + c - y - y - y = 253*y + c

            ; Update seed
            cpl
            ld (hl),a   ; q[i] = -A
            ; Update carry, c = D
            ld c,d
            ; Update index, i = (i+1) & 7
            inc b
            res 3,b
            ; save (i,c)
            ld (_cmwc8_var),bc
            ret

_cmwc8_seed DB &4b,&61,&72,&75,&6b,&65,&72,&61

Seed generator

Your PRNG will be as good as its seed. So it is important to know how to produce quality seed values.

Memory hash

If the Firmware (or anything like it) is or was running in the background and all of its variables and buffers are still in memory, performing a checksum or hash of all this junk gives a pretty good seed value.

Trackloader

Real mechanical disc drives can make for a nice source of entropy. If your program uses a custom trackloader, all of its waiting loops can be turned into a seed generator.

Large Seed generator

If LFSR PRNGs can quickly be seeded directly with a eg. a memory hash or, blergh, a crap RNG, the XorShift128 and CMWC require multi-bytes long seed.

The best way to seed these PRNG, usually at the very beginning of your program, is to combine as much entropy-sources as you can (memory hash, disc drive, interrupts, video timings, …) to seed a tiny LFSR which in turn will be used to generate a large seed value. Yo dawg!

PRNG in games

Player entropy

In most case, with a good PRNG, you can just get away with the generated sequence number as-is. However, in some particular cases, your program might still display undesirable predictability / similar patterns. This is often happening with simple LFSR PRNG.

The generated sequence of numbers, therefore the seed, should be changed from time to time in order to improve the apparent randomness. To do that, you have to modify the seed when an unpredictable event occurs in your program. In a game, the human player is an excellent source of entropy: modify the seed in some way when eg. fire is pressed, in some other way when the player gets hit, etc until it looks good.

Map generator

Did you know that the maps in the game Boulder Dash are, in most part, generated with a random number generator? Each map initializes the seed to a specific value and the corresponding sequence of numbers will be used to place dirt, boulder, empty space or diamond into each cell of the map! A whole map generated from a single byte!

Changelog

  • 2020-11-xx – Recycled by MrEarwig