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 (http://lronaldo.github.io/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 (https://en.wikipedia.org/wiki/Multiply-with-carry#Complementary-multiply-with-carry_generators) 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
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
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
Quote from: Grim on 13:48, 19 October 15
See CMWC on Wikipedia (https://en.wikipedia.org/wiki/Multiply-with-carry#Complementary-multiply-with-carry_generators) 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 (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 (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.
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. :)