Printed Amstrad Addict magazine announced, check it out here!

Main Menu

Pseudo-random number generation

Started by ronaldo, 12:51, 19 October 15

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.


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?


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.

;; 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

; 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
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
DB &4b,&61,&72,&75,&6b,&65,&72,&61


Ported from U4 and 6502-Assembler.

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

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

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

Alcoholics Anonymous

Quote from: Grim on 13:48, 19 October 15
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:

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:

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.


Quote from: ronaldo on 12:51, 19 October 15
   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.  :)
TFM of FutureSoft
Also visit the CPC and Plus users favorite OS: FutureOS - The Revolution on CPC6128 and 6128Plus

Powered by SMFPacks Menu Editor Mod