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 idea” famous 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
retCrapified 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
retThis 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
retXorShift
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,&10XorShift 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<<13X ^= X>>17X ^= X<<15- New 32-bit random number in
X
64-bit
- Two 32-bit seeds :
XandY - Algorithm
T = X^(X<<10)X = YY = (Y^(Y>>10))^(T^(T>>13))- New 32-bit random number in
Y
96-bit
- Three 32-bit seeds :
X,YandZ - Algorithm
T = (X^(X<<10))X = YY = ZZ = (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.
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,&61Seed 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
