Author Topic: Pseudo-random number generation  (Read 1345 times)

0 Members and 1 Guest are viewing this topic.

Offline ronaldo

  • Dev
  • 6128 Plus
  • *****
  • Posts: 648
  • Country: es
    • Profesor Retroman
  • Liked: 941
  • Likes Given: 827
Pseudo-random number generation
« on: 14:51, 19 October 15 »
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.
[youtube]https://www.youtube.com/watch?v=WiTLxV4UDe8[/youtube]
   Do you have any other great pseudo-random number generators?

Offline Grim

  • CPC6128
  • ****
  • Posts: 202
  • Country: gp
  • La pak ba, bèf ka pasé
    • THERE IS NO GAME
  • Liked: 134
  • Likes Given: 67
Re: Pseudo-random number generation
« Reply #1 on: 15: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.

Code: [Select]
;; 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

Offline Fessor

  • CPC6128
  • ****
  • Posts: 234
  • Country: de
  • Liked: 204
  • Likes Given: 46
Re: Pseudo-random number generation
« Reply #2 on: 16:45, 19 October 15 »
Ported from U4 and 6502-Assembler.

Code: [Select]
; 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



Offline Alcoholics Anonymous

  • CPC664
  • ***
  • Posts: 51
  • Country: ca
  • Liked: 44
  • Likes Given: 0
Re: Pseudo-random number generation
« Reply #3 on: 20:59, 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.
« Last Edit: 21:04, 19 October 15 by Alcoholics Anonymous »

Offline TFM

  • Visit the mysteries of the CPC at www.futureos.de
  • Supporter
  • 6128 Plus
  • *
  • Posts: 9.899
  • Country: aq
  • Space Chicken for FutureOS is free!
    • index.php?action=treasury
    • FutureOS - The revolution on CPC!
  • Liked: 1983
  • Likes Given: 4650
Re: Pseudo-random number generation
« Reply #4 on: 17:42, 20 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