## Pseudo-random number generation

Started by ronaldo, 12:51, 19 October 15

0 Members and 1 Guest are viewing this topic.

#### 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.

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

`; 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    retrnd0        db &64rnd1        db &76rnd2        db &85rnd3        db &54,&f6,&5c,&76,&1f,&e7,&12,&a7,&6b,&93,&c4,&6erndf        db &1b`

#### Alcoholics Anonymous

#3
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:
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

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