Home > Z80 Assembly > Random number generators

Random number generators

The random number generators given here originally appeared as posts by Patrik Rak on WoSF and are used here with permission.

The default built-in pseudo random number generator in the ZX Spectrum cycles through 65536 numbers (2^16 sequence of numbers). Patrik proposes two alternatives for better random number generation starting with the XOR shift method (based on George Marsaglia’s derivation), in assembly for the Z80:

Yesterday I had a bit of spare time so I put together a quick test for finding the a,b,c parameters for n=8 and four seeds (I first verified the Marsaglia’s 81 parameters to make sure I got it all right). There are six sets of parameters which provide the desired order of 2^32-1: (1,1,3), (3,6,1), (3,3,2), (5,3,2), (1,7,2), (6,7,1). Of these, the first four seem to do reasonably well on the Diehard test. Here is the Z80 code for the (1,1,3) variant, the result being the 8 bit in the A register:

rnd     ld  hl,0xA280   ; xz -> yw
        ld  de,0xC0DE   ; yw -> zt
        ld  (rnd+1),de  ; x = y, z = w
        ld  a,e         ; w = w ^ ( w << 3 )
        add a,a
        add a,a
        add a,a
        xor e
        ld  e,a
        ld  a,h         ; t = x ^ (x << 1)
        add a,a
        xor h
        ld  d,a
        rra             ; t = t ^ (t >> 1) ^ w
        xor d
        xor e
        ld  h,l         ; y = z
        ld  l,a         ; w = t
        ld  (rnd+4),hl
        ret

In order to return the 8 bit random number to BASIC, do a LD B,0 and LD C, A just before the RET in the end.

Seeing the interest regarding the Xor-Shift random number generator for Z80, I became curious how difficult it would be to implement CMWC (Complimentary-Multiply-With-Carry) RNG for Z80. These generators are based on a prime p of the form a*b^r + 1, carry c < a and a sequence of r x’s < b such that t = a * x(n-r) + c(n-1), c(n) = t div b, x(n) = (b-1) – t mod b.

To make it suitable for Z80, I have chosen base b=2^8. I was also interested how well it could do with fairly small state, so I have chosen r=8 rather than the tempting r=256. From the possible primes, I have chosen the one with a=253, for which the order of the generated sequence is (p-1)/2^5 = 253*2^59 (assuming I got all the math right ), which is almost 2^67, and more than 2^66 or 10^20.

I have tested the C version of the generator with diehard, and it seems to pass all the tests. Here is the corresponding Z80 variant, which returns the 8 bit result in A:

org 40000

    call rnd      ; BASIC driver
    ld   c,a
    ld   b,0
    ret

rnd ld   de,0     ; c,i

    ld   b,0
    ld   c,e
    ld   hl,table
    add  hl,bc

    ld   c,(hl)   ; y = q[i]

    push hl

    ld   a,e      ; i = ( i + 1 ) & 7
    inc  a
    and  7
    ld   e,a

    ld   h,c      ; t = 256 * y
    ld   l,b

    sbc  hl,bc    ; t = 255 * y
    sbc  hl,bc    ; t = 254 * y
    sbc  hl,bc    ; t = 253 * y

    ld   c,d
    add  hl,bc    ; t = 253 * y + c

    ld   d,h      ; c = t / 256

    ld   (rnd+1),de

    ld   a,l      ; x = t % 256
    cpl           ; x = (b-1) - x = -x - 1 = ~x + 1 - 1 = ~x

    pop  hl

    ld   (hl),a   ; q[i] = x

    ret

table
    db   82,97,120,111,102,116,20,12

As you can see, the table access is quite expensive compared to the computation itself. Having the table aligned to 256 byte boundary could be used to optimize this. Also, when generating more than 8 bits at once, most of this could be easily factored out and reused. But I leave these optimizations for anyone interested…

The original posts contain some more tidbits that may be of use including BASIC and ZX Boriel Compiler versions:
http://www.worldofspectrum.org/forums/showthread.php?t=23070

http://www.worldofspectrum.org/forums/showthread.php?t=39632

 

Advertisements
Categories: Z80 Assembly Tags: , , ,
  1. sykobee
    July 5, 2012 at 7:56 pm

    My Z80 is very basic, but if I read it right, to seed the second routine, before calling it you could do:

    ld bc, (seed)
    ld (rnd+1),bc
    call rnd

    ?

    • July 6, 2012 at 6:25 pm

      Sounds about right.

    • Patrik Rak
      August 9, 2012 at 1:42 pm

      No, that might set c to a value >= a and i to a value > 7, both of which are wrong. While the former just breaks the preconditions of the theory behind this generator and might actually work just as well (subject to the values of x’s in the table), the latter would mess the memory after the table outright, which is definitely bad.

      To seed the second one, just set the 8 bytes in the table (or just some of them, like the first two) to some randomly chosen values. Any values, including all zeroes and all 255, are valid, so you don’t have to worry about that.

  2. Patrik Rak
    March 10, 2015 at 2:12 pm

    BTW, the code posted here has been slightly optimized in the meantime, so if you are looking for the latest version, check the WoS threads mentioned above.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: