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 pseudorandom 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 pseudorandom 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 fullperiod 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.
Memotest 2017  Z80 coding contest

 Posts: 54
 Joined: 08 Jan 2014, 20:50
Memotest 2017  Z80 coding contest
Last edited by Tony Brewer on 25 Oct 2017, 00:26, edited 11 times in total.

 Posts: 54
 Joined: 08 Jan 2014, 20:50
Re: Memotest 2017  Z80 coding contest
Basic challenge
Write code for a routine called PRNG16. p, q and the PRN are all 16bit. Remember a new PRN is obtained just by adding the new p and q. Ignore the carry from the addition as it is very unrandom. p, q and the PRN should be kept in registers. You can use whichever you prefer, however see rules below.
The [a,b,c] constants are [14,2,7].
To check your code is working, here are the first sixteen PRNs when the seed is p = 1, q = 0:
4085, 5530, 2C7C, 769F, A248, DFFD, 202D, F2F1, 5ACA, 4DC8, D1D1, ADCD, 0598, 1B30, 8094, 540C
It will take 2^321 or 4294967295 iterations before the p and q outputs are the same as the initial p and q inputs.
Advanced challenge (optional)
A feature of this PRNG algorithm is that the more significant the bit or byte, the more random it is. Bit 0 fails a particular randomness test and a higherquality 16bit result can be achieved by combining the high bytes from two successive iterations.
An alternative that should be faster is to use 17bit p and q, add them and throw away the lsb to give a higherquality 16bit PRN in one go. The advanced test is to write such a routine called PRNG17.
The [a,b,c] constants are [7,8,12].
Here are the first sixteen PRNs (top 16 bits of 17bit sum) when the seed is p = 1, q = 0:
08C0, B046, 53AE, 5FB4, E38E, AC74, 1479, E254, E127, A736, FC9C, F89A, 3D47, 3466, AA02, EC84
It will take 2^341 or 17179869183 iterations before the p and q outputs are the same as the initial p and q inputs.
Write code for a routine called PRNG16. p, q and the PRN are all 16bit. Remember a new PRN is obtained just by adding the new p and q. Ignore the carry from the addition as it is very unrandom. p, q and the PRN should be kept in registers. You can use whichever you prefer, however see rules below.
The [a,b,c] constants are [14,2,7].
To check your code is working, here are the first sixteen PRNs when the seed is p = 1, q = 0:
4085, 5530, 2C7C, 769F, A248, DFFD, 202D, F2F1, 5ACA, 4DC8, D1D1, ADCD, 0598, 1B30, 8094, 540C
It will take 2^321 or 4294967295 iterations before the p and q outputs are the same as the initial p and q inputs.
Advanced challenge (optional)
A feature of this PRNG algorithm is that the more significant the bit or byte, the more random it is. Bit 0 fails a particular randomness test and a higherquality 16bit result can be achieved by combining the high bytes from two successive iterations.
An alternative that should be faster is to use 17bit p and q, add them and throw away the lsb to give a higherquality 16bit PRN in one go. The advanced test is to write such a routine called PRNG17.
The [a,b,c] constants are [7,8,12].
Here are the first sixteen PRNs (top 16 bits of 17bit sum) when the seed is p = 1, q = 0:
08C0, B046, 53AE, 5FB4, E38E, AC74, 1479, E254, E127, A736, FC9C, F89A, 3D47, 3466, AA02, EC84
It will take 2^341 or 17179869183 iterations before the p and q outputs are the same as the initial p and q inputs.
Last edited by Tony Brewer on 26 Oct 2017, 20:29, edited 21 times in total.

 Posts: 54
 Joined: 08 Jan 2014, 20:50
Re: Memotest 2017  Z80 coding contest
Programming rules
1. Your routine must exit with the new p and q in the same registers as they were on entry. The new PRN is an output only, p and q are both inputs and outputs.
(Most people used DE = p, BC = q, HL = PRN in the Basic challenge.)
2. Your routine must not contain selfmodifying code as it should be able to run entirely in ROM.
3. Your routine must be selfcontained and not call or jump to any address outside the routine itself.
4. Your routine must run correctly if placed anywhere in memory.
5. Your routine must run correctly thousands of millions of times.
1. Your routine must exit with the new p and q in the same registers as they were on entry. The new PRN is an output only, p and q are both inputs and outputs.
(Most people used DE = p, BC = q, HL = PRN in the Basic challenge.)
2. Your routine must not contain selfmodifying code as it should be able to run entirely in ROM.
3. Your routine must be selfcontained and not call or jump to any address outside the routine itself.
4. Your routine must run correctly if placed anywhere in memory.
5. Your routine must run correctly thousands of millions of times.
Last edited by Tony Brewer on 25 Oct 2017, 00:27, edited 13 times in total.

 Posts: 54
 Joined: 08 Jan 2014, 20:50
Re: Memotest 2017  Z80 coding contest
Contest Rules
1. Please do NOT post any of the following either here or on the Memotech Facebook page:
* Your source code
* Tips or spoilers
* The number of bytes in your solution
2. Send your source code to me by a private message here or on Facebook (click on my name) any time before the end of Friday October 13th 2017.
3. I prefer Z80 instructions to be in uppercase, indented by one tab. Multiple entries are allowed, should you find a better solution. Please include in the source code your name and the number of bytes in your routine (excluding RET).
4. The Basic or Advanced winner will be the person or persons who can beat or match my smallest code for the Basic or Advanced challenge, to be announced during Memofest. The number of Tstates will act as a tiebreaker, if necessary.
1. Please do NOT post any of the following either here or on the Memotech Facebook page:
* Your source code
* Tips or spoilers
* The number of bytes in your solution
2. Send your source code to me by a private message here or on Facebook (click on my name) any time before the end of Friday October 13th 2017.
3. I prefer Z80 instructions to be in uppercase, indented by one tab. Multiple entries are allowed, should you find a better solution. Please include in the source code your name and the number of bytes in your routine (excluding RET).
4. The Basic or Advanced winner will be the person or persons who can beat or match my smallest code for the Basic or Advanced challenge, to be announced during Memofest. The number of Tstates will act as a tiebreaker, if necessary.
Last edited by Tony Brewer on 22 Oct 2017, 16:36, edited 13 times in total.

 Posts: 54
 Joined: 08 Jan 2014, 20:50
Re: Memotest 2017  Z80 coding contest
Is there any restriction on self modifying code?
THIS is what Memotech is doing now.

 Posts: 54
 Joined: 08 Jan 2014, 20:50
Re: Memotest 2017  Z80 coding contest
Selfmodifying code is not allowed in the basic challenge code, which should be able to run in ROM.

 Posts: 54
 Joined: 08 Jan 2014, 20:50
Re: Memotest 2017  Z80 coding contest
New programming rules added to post 2 above.
Re: Memotest 2017  Z80 coding contest
Are the "undocumented" Z80 instructions allowed?
Things like: LD IXh, A (0xDD, 0x67)
Or "Official" Z80 instructions only?
Things like: LD IXh, A (0xDD, 0x67)
Or "Official" Z80 instructions only?

 Posts: 54
 Joined: 08 Jan 2014, 20:50
Re: Memotest 2017  Z80 coding contest
Any code that will run on a Z80A CPU is permitted, including "undocumented" instructions.
Who is online
Users browsing this forum: No registered users and 1 guest