Memotest 2017 - Z80 coding contest
Posted: 24 Sep 2017 20:33
EDIT:
The competition has now closed but if you have just found this page and enjoy Z80 programming why not have a go anyway?
Memotest 2017
This is a Z80 assembly language challenge, intended to be a fun test of your ability to write the smallest and fastest code possible for a pseudo-random number generator (PRNG) using an algorithm invented in 2016.
This algorithm differs from a simple linear feedback shift register (LFSR) in at least two respects: how it works and its vastly improved quality. Instead of using the previous pseudo-random number (PRN) to generate the next, there are two variables, p and q, that are added together to give the PRN. The next state is derived from the current state as follows:
p := (p ROL a) XOR (p SHL b) XOR (q SHL b) XOR p XOR q
q := (p ROL c) XOR (q ROL c)
where
p ROL a = p rotated left by a bits
p SHL b = p shifted left by b bits (arithmetic)
q SHL b = q shifted left by b bits (arithmetic)
p ROL c = p rotated left by c bits
q ROL c = q rotated left by c bits
a, b and c are constants.
p and q have the same number of bits.
A set of constants can be chosen so that the sequence is full-period and the resulting PRNs perform best in randomness tests. The initial state or seed cannot be all zeroes, thus p = 0, q = 0 is not allowed. Although the seed cannot be zero, the PRN can be.
Hint
XOR is associative and commutative.
The competition has now closed but if you have just found this page and enjoy Z80 programming why not have a go anyway?
Memotest 2017
This is a Z80 assembly language challenge, intended to be a fun test of your ability to write the smallest and fastest code possible for a pseudo-random number generator (PRNG) using an algorithm invented in 2016.
This algorithm differs from a simple linear feedback shift register (LFSR) in at least two respects: how it works and its vastly improved quality. Instead of using the previous pseudo-random number (PRN) to generate the next, there are two variables, p and q, that are added together to give the PRN. The next state is derived from the current state as follows:
p := (p ROL a) XOR (p SHL b) XOR (q SHL b) XOR p XOR q
q := (p ROL c) XOR (q ROL c)
where
p ROL a = p rotated left by a bits
p SHL b = p shifted left by b bits (arithmetic)
q SHL b = q shifted left by b bits (arithmetic)
p ROL c = p rotated left by c bits
q ROL c = q rotated left by c bits
a, b and c are constants.
p and q have the same number of bits.
A set of constants can be chosen so that the sequence is full-period and the resulting PRNs perform best in randomness tests. The initial state or seed cannot be all zeroes, thus p = 0, q = 0 is not allowed. Although the seed cannot be zero, the PRN can be.
Hint
XOR is associative and commutative.