cpct_nextRandom_mxor_u8

Calculates next 32-bits state for a Marsaglia’s XOR-Shift pseudo-random 8-bits generator, with the tuple (1,1,3) .

C Definition

u32 cpct_nextRandom_mxor_u8 (u32 seed) __z88dk_fastcall;

Input Parameters (4 bytes)

Assembly call (Input parameter on DE:HL)

call cpct_nextRandom_mxor_u8_asm

Return value (Assembly calls, return DE:HL = seed, A=L=random 8-bits)

Parameter Restrictions

• state could be any 32-bits number except 0.  A 0 as input will always produce another 0 as output.

Important details

• This function calculates next state in a 32-bits sequence that goes over all 32-bits possible states except 0.  Therefore, it has a repeating period of (2^32)-1.  The walk this function does has a high pseudo-random quality, measured using Dieharder tests: (99 passed, 4 weak, 11 failed).  Giving 3 points per passed test and 1 point per weak result, the algorithm gets 301 out of 342 points (88.01%).
• The quality of the pseudo-random 8-bits sequence is somewhat worse than that produced by other functions like cpct_getRandom_mxor_u8 (which uses cpct_nextRandom_mxor_u32) and cpct_getRandom_xsp40_u8, but still has a very good quality with with a really low CPU cost.  It is recommended with highest quality is not required, but CPU cost is a must.  In fact, quality compared to cpct_getRandom_glfsr16_u8 and cpct_getRandom_lcg_u8 is several orders of magnitude higher.

Details

This function implements a sequence of 32-bits states with period (2^32)-1.  For each produced state, a random sequence of 8-bits is returned.  This means that it produces consecutive 8-bits values that do not repeat until 4.294.967.295 numbers have been generated.  To do this, the function receives a 32-bit state as parameter (that should be different from 0) and returns the next 32-bit value in the sequence.  In each returned state, the 8 Least Significant bits are the 8 pseudo-random bits produced.

The sequence calculated by this function is based on a modified version of Marsaglia’s XOR-shift generator using the tuple (3, 1, 1) for 8-bit values.  This tuple is implemented really fast on a Z80 (Patrik Rak originally showed a similar implementation for tuple (1, 1, 3)).  Assuming that the 32-bits state s is composed of 4 8-bits numbers s=(x, z, y, w), this algorithm produces a new state s’=(x’,z’,y’,w’) doing these operations:

x' = y;
y' = z;
z' = w;
t  = x ^ (x << 3);
t  = t ^ (t >> 1);
w' = w ^ (w << 1) ^ t;

where <</>> are left/right bit shifting operations, and ^ is the exclusive OR (XOR) bitwise operation.

Destroyed Register values

AF, BC, DE, HL

Required memory

17 bytes

Time Measures

   Case     | microSecs (us) | CPU Cycles
-----------------------------------------
   Any      |      19        |    76
-----------------------------------------

Random quality measures

• Dieharder tests rank: (99 Pass, 4 Weak, 11 Failed) (301/342 = 88.01%)
• Pseudo-random bit stream velocity: 2,375 us / bit.  (8 bits produced in 19 us)

Credits

• Original XOR-shifting algorithm published by George Marsaglia
• Initial code for the 8-bits version of (1,1,3) tuple from Patrik Rak (World of Spectrum forums)