Pseudo-random number generation

[ronaldo]

Hi all,

   This weekend I was reviewing the simple pseudo-random number generators that are used here and there for game development under Z80 platforms. I was thinking about the posibility of having better quality random numbers without involving a great CPU or memory cost (like a Mersenne Twister would require, for instance).

   I implemented a Galois Linear-Feedback Shift Register (G-LFSR), which is extremely fast (19/26 us) and has a 65535 period for 16.bits numbers, which is great. However, the random traversal is not exactly "random", and is fairly predictable. In fact, it sometimes gives up to 0 consecutive zeroes (when using only 8 bits), which is usually not desirable. Anyways, it is a great algorithm and has a many advantages.

   Then I made a combination of this algorithm with the previous simple Linear Congruential Generator (LCG) that CPCtelera had (similar to ZX ROM random generator), and the combination of both is really great. I've made a video showing them three. From left to right you have LCG, G-LFSR (with 1 out of 1024 possible traversals) and Mixed Generator. The final combination takes 46 us and 39 bytes, and I think is a really great performance.

   Do you have any other great pseudo-random number generators?

[Grim]

See CMWC on Wikipedia for more detail on the algorithm. Below is a 8-bit implementation. Randomness wise, when seeded properly, it beats LFSR-based PRNG.

Code Select Expand


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

rnd8_cmwc:
; Init (i,c)
_rnd8_cmwc_var EQU $ + 1
ld bc,0
; Read q[i]
ld hl,_rnd8_cmwc_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 (_rnd8_cmwc_var),bc
ret
_rnd8_cmwc_seed
DB &4b,&61,&72,&75,&6b,&65,&72,&61


[Fessor]

Ported from U4 and 6502-Assembler.

Code Select Expand


; returns 8-bit-Random in A
; hl and bc saved
;

rand   
    push hl
    push bc
    ld a,(rndf)
    ld b,&f
    ld c,0
    ld hl,rnd0+&e
_rnd_add
    adc a,(hl)
    ld (hl),a
    dec hl
    djnz _rnd_add
    ld b,&10
    ld hl,rnd0
_rnd_inc
    inc (hl)
    inc hl
    djnz _rnd_inc
    ld a,(rnd0)
    and a
    pop bc
    pop hl
    ret


rnd0   
    db &64
rnd1   
    db &76
rnd2   
    db &85
rnd3   
    db &54,&f6,&5c,&76,&1f,&e7,&12,&a7,&6b,&93,&c4,&6e
rndf   
    db &1b

[Alcoholics Anonymous]

See CMWC on Wikipedia for more detail on the algorithm. Below is a 8-bit implementation. Randomness wise, when seeded properly, it beats LFSR-based PRNG.

You can see a little bit cleaner implementation in z88dk:
http://z88dk.cvs.sourceforge.net/viewvc/z88dk/z88dk/libsrc/_DEVELOPMENT/stdlib/z80/random/asm_random_uniform_cmwc_8.asm?revision=1.2&content-type=text%2Fplain

The self-modfying code is eliminated so that independent random number sequences can be generated.  It's a little bit faster too.  Patrik Rak wrote this several years ago.


Marsaglia xor shift generators are also high quality and very fast on the z80 when auspicious triples are chosen.  Here's one with a 32-bit seed and result:
http://z88dk.cvs.sourceforge.net/viewvc/z88dk/z88dk/libsrc/_DEVELOPMENT/stdlib/z80/random/asm_random_uniform_xor_32.asm?revision=1.2&content-type=text%2Fplain

The link in that source will take you to Marsaglia's original paper describing how it works.  This is the one we use for C's rand() function as we can take this result in 1...2^32-1 and return a uniform random number in 0..32767 (it includes zero) required by the C standard.  To generate something similar with the CMWC we'd have to call that twice in a row which makes it slower as well as it's not impossible that combination of two successively generated numbers might degrade the quality (but this has not been tested with diehard; CMWC has very good characteristics so maybe not).  The version in sdcc is a tradition LCG generator which is slower and lower quality.  They recently updated (or are testing) a Marsaglia generator but in C.

The other generators you find on the net are mainly junk and surprisingly tend to be slower than these much higher quality ones.  The CMWC in particular was a surprise to see implemented so compactly.

[TFM]

   Do you have any other great pseudo-random number generators?

Yes, got one, can you send me the application you made these pictues, then I will do the same. I mean I will inegrate my random generator and send that back to you. My camera is not as good.