At last, it seems I have the perfect random numbers generator for Z80.

A couple of years ago, I discovered John Metcalf's 16 bits random numbers generator (based on George Marsaglia's xorshift), it is small and fast:

; generates 16-bit pseudorandom numbers with a period of 65535
; using the xorshift method:

; hl ^= hl << 7
; hl ^= hl >> 9
; hl ^= hl << 8

_xrnd:
ld hl,1 ; seed must not be 0
ld a,h
rra
ld a,l
rra
xor h
ld h,a
ld a,l
rra
ld a,h
rra
xor l
ld l,a
xor h
ld h,a
ld (_xrnd+1),hl
ret

, but I needed also a good-enough 'set-seed-value' routine (to set the initial value at _xrnd+1).

Until now, I loaded the seed value from 0C000H (for a RC2014) or added the screen characters (for Z80ALL). Not good enough, true?

The last weekend I read (I do not remember exactly where...) a hint about using the Z80 R register, for this purpose.

So, here it is, the set-seed-value routine:

_xrndseed:
ld a,r
ld l,a
ld a,r
ld h,a
or l ; HL must be not NULL
jr nz,1f
inc hl
1:
ld (_xrnd+1),hl
ret

I used these routines for my last game (TextFall), and they work perfectly.

I mean, each game starts with a new visual configuration, different form the last one ( it will be boring to play-it allways starting from the same setup, no ? )

Interesting, it works also on Z80SIM! (very good work, Udo!).

In fact, I'm away on vacation, and I only have my laptop with me (not also a RC2014...) ; however, I managed these days to write TextFall, which uses the new random numbers generator, only using Z80SIM.

I wonder how many Z80 simulators/emulators will correctly execute the 'ld a,r' instruction ? It's all about how the simulator implements the R register...

Can anyone test-it on other Z80 simulators?

Ladislau

PS. Once returned from vacation, I will update all the games I published lately, to benefit from the new random numbers generator...

One comment, using the R register twice like that, the value you get in H is going to be deterministically derived from L, in that you have a fixed set of instructions between the two "ld a,r" instructions so the second sampling of R is going to be a constant incremental value different from the first sampling (you might as well just add a constant). Also note that the R register only counts across 7 bits, so the 8th bit of that register won't change. One good source of a seed for games is to require the user to press a key to "start", and then you use the amount of "time" it takes to get that key-press to generate a seed.

Note that Linux uses multiple sources of "entropy" to feed the random number generators. But, taking Linux as an example, you have input from "human interface devices", networks, and disk I/O (rotational latency) all feeding the entropy based on how long it takes to complete operations that simulate randomness. Of course, solid-state storage (CF, SDCard) does not have rotational latency, so they don't work well for entropy.

ladislau szilagyi schrieb am Freitag, 4. August 2023 um 13:13:57 UTC+2:
> Interesting, it works also on Z80SIM! (very good work, Udo!).
Some software we were using in the 80s used R, so I implemented it to get correct results.
Please note that versions before 1.38-dev changed all 8 bits, the real Z80 changes 7 bits
and you could use bit 8 on your own, this was corrected in 1.38-dev.

ladislau szilagyi <ladislau_szilagyi@euroqst.ro> wrote:

> At last, it seems I have the perfect random numbers generator for Z80.

It looks fast at least. I presume it's based on this, or the
retroprogramming.com page it links to:

https://github.com/impomatic/xorshift798

Unfortunately I can't see any licence specified anywhere, which
seems troublesome. Perhaps an oversight.

> George Marsaglia's xorshift

Funnily enough, I did a Z80 version of a 32-bit xorshift from
"Xorshift RNGs" for my zcsoli game (arguably a silly choice, as it
only uses half of that).

Another RNG I like is Chris Doty-Humphrey's sfc_v3_16 from PractRand,
which seems to stand up surprisingly well to randomness testing while
still being fairly fast when converted to Z80 (though it's over twice
the size of the routine you posted, and significantly slower). His
original and my port are both public domain. I used it in ZCN 1.4's
cpmtris and zcnlib:

https://zgedneil.nfshost.com/zcn.html

Speaking of PractRand, I'll just go well overboard here :-) and show
how "RNG_test" from that assesses the randomness of sfc_v3_16 and
xorshift32 (which I would intuitively expect to give better results
than the 16-bit xorshift798, given the similar algorithm). This is
just one run each, but it gives you the idea I think:

rus@wedge:1001:/home/rus>RNG_test xorshift32
RNG_test using PractRand version 0.95
RNG = xorshift32, seed = 0x697d15c6
test set = core, folding = standard (32 bit)

rng=xorshift32, seed=0x697d15c6
length= 64 megabytes (2^26 bytes), time= 2.8 seconds
Test Name Raw Processed Evaluation
BCFN(2+0,13-3,T) R= +45.9 p = 1.5e-21 FAIL !!
BCFN(2+1,13-3,T) R= +8.4 p = 9.2e-4 unusual
DC6-9x1Bytes-1 R=+471.6 p = 3.8e-300 FAIL !!!!!!
BRank(12):128(4) R= +3922 p~= 8e-2087 FAIL !!!!!!!!
BRank(12):256(2) R= +6670 p~= 5e-2009 FAIL !!!!!!!!
BRank(12):384(1) R= +7472 p~= 2e-2250 FAIL !!!!!!!!
BRank(12):512(2) R=+14464 p~= 4e-4355 FAIL !!!!!!!!
BRank(12):768(1) R=+15738 p~= 8e-4739 FAIL !!!!!!!!
BRank(12):1K(1) R=+21249 p~= 9e-6398 FAIL !!!!!!!!
[Low8/32]BRank(12):128(4) R= +3922 p~= 8e-2087 FAIL !!!!!!!!
[Low8/32]BRank(12):256(2) R= +6670 p~= 5e-2009 FAIL !!!!!!!!
[Low8/32]BRank(12):384(1) R= +7472 p~= 2e-2250 FAIL !!!!!!!!
[Low8/32]BRank(12):512(2) R=+14464 p~= 4e-4355 FAIL !!!!!!!!
[Low8/32]BRank(12):768(1) R=+15738 p~= 8e-4739 FAIL !!!!!!!!
[Low1/32]BRank(12):128(2) R= +2773 p~= 6.9e-836 FAIL !!!!!!!
[Low1/32]BRank(12):256(2) R= +6670 p~= 5e-2009 FAIL !!!!!!!!
[Low1/32]BRank(12):384(1) R= +7472 p~= 2e-2250 FAIL !!!!!!!!
...and 125 test result(s) without anomalies

rus@wedge:1002:/home/rus>RNG_test sfc_v3_16
RNG_test using PractRand version 0.95
RNG = sfc_v3_16, seed = 0x9d9758a7
test set = core, folding = standard (16 bit)

rng=sfc_v3_16, seed=0x9d9758a7
length= 64 megabytes (2^26 bytes), time= 3.0 seconds
no anomalies in 146 test result(s)

rng=sfc_v3_16, seed=0x9d9758a7
length= 128 megabytes (2^27 bytes), time= 7.5 seconds
no anomalies in 159 test result(s)

rng=sfc_v3_16, seed=0x9d9758a7
length= 256 megabytes (2^28 bytes), time= 14.8 seconds
no anomalies in 172 test result(s)

rng=sfc_v3_16, seed=0x9d9758a7
length= 512 megabytes (2^29 bytes), time= 27.6 seconds
Test Name Raw Processed Evaluation
[Low4/16]FPF-14+6/16:all R= +5.1 p = 3.0e-4 unusual
...and 184 test result(s) without anomalies

rng=sfc_v3_16, seed=0x9d9758a7
length= 1 gigabyte (2^30 bytes), time= 52.0 seconds
no anomalies in 198 test result(s)

rng=sfc_v3_16, seed=0x9d9758a7
length= 2 gigabytes (2^31 bytes), time= 98.8 seconds
no anomalies in 210 test result(s)

rng=sfc_v3_16, seed=0x9d9758a7
length= 4 gigabytes (2^32 bytes), time= 190 seconds
no anomalies in 222 test result(s)

rng=sfc_v3_16, seed=0x9d9758a7
length= 8 gigabytes (2^33 bytes), time= 375 seconds
no anomalies in 233 test result(s)

[...and so on.]

So, while the routine being (in that Z80 port) slower and twice as big
is clearly an issue, at least according to PractRand itself that does
seem to buy you quite an improvement in the quality of the output.

Does this matter in a game? Maybe not. But I think it's worth noting.

> I wonder how many Z80 simulators/emulators will correctly execute
> the 'ld a,r' instruction ?

That should really be supported by any full Z80 emulation, so it's
unlikely to be a problem. It's an important one to emulate due to uses
like this, and because you can potentially use the top bit to store
data. And it even gives you a way of checking whether interrupts were
previously enabled or not in e.g. an NMI handler.

-Rus.

On Saturday, August 5, 2023 at 1:56:30 PM UTC-5, Russell Marks wrote:
>... And it even gives you a way of checking whether interrupts were
> previously enabled or not in e.g. an NMI handler.
>
> -Rus.

The Z80 CPU already does this for NMI, as long as you use RETN to return from the NMI handler. You can't enter any other interrupt handler unless interrupts are enabled, so you always know how to return from those (EI/RET or EI/RETI).

On Friday, August 4, 2023 at 7:13:57 AM UTC-4, ladislau szilagyi wrote:
> At last, it seems I have the perfect random numbers generator for Z80.
>
> A couple of years ago, I discovered John Metcalf's 16 bits random numbers generator (based on George Marsaglia's xorshift), it is small and fast:
>
> ; generates 16-bit pseudorandom numbers with a period of 65535
> ; using the xorshift method:
>
> ; hl ^= hl << 7
> ; hl ^= hl >> 9
> ; hl ^= hl << 8
>
> _xrnd:
> ld hl,1 ; seed must not be 0
> ld a,h
> rra
> ld a,l
> rra
> xor h
> ld h,a
> ld a,l
> rra
> ld a,h
> rra
> xor l
> ld l,a
> xor h
> ld h,a
> ld (_xrnd+1),hl
> ret
>
> , but I needed also a good-enough 'set-seed-value' routine (to set the initial value at _xrnd+1).
>
> Until now, I loaded the seed value from 0C000H (for a RC2014) or added the screen characters (for Z80ALL). Not good enough, true?
>
> The last weekend I read (I do not remember exactly where...) a hint about using the Z80 R register, for this purpose.
>
> So, here it is, the set-seed-value routine:
>
> _xrndseed:
> ld a,r
> ld l,a
> ld a,r
> ld h,a
> or l ; HL must be not NULL
> jr nz,1f
> inc hl
> 1:
> ld (_xrnd+1),hl
> ret
>
> I used these routines for my last game (TextFall), and they work perfectly.
>
> I mean, each game starts with a new visual configuration, different form the last one ( it will be boring to play-it allways starting from the same setup, no ? )
>
> Interesting, it works also on Z80SIM! (very good work, Udo!).
>
> In fact, I'm away on vacation, and I only have my laptop with me (not also a RC2014...) ; however, I managed these days to write TextFall, which uses the new random numbers generator, only using Z80SIM.
>
> I wonder how many Z80 simulators/emulators will correctly execute the 'ld a,r' instruction ? It's all about how the simulator implements the R register...
>
> Can anyone test-it on other Z80 simulators?
>
> Ladislau
>
> PS. Once returned from vacation, I will update all the games I published lately, to benefit from the new random numbers generator...

I tried it using Simeon Cran's MyZ80, and it appears to work correctly. For testing purposes, I made only a single retrieval of the R register's value, storing it in the low byte of the HL register pair:

db 0edh,5fh ; Z-80 LD A,R instruction
mov l,a ; move result to HL
mvi h,0 ; don't sign extend
shld _rnext ; store it
ret ; we're done

In 10 invocations of the test program, the resulting seed values were 114, 101, 81, 51, 105, 102, 23, 57, 51, and 48. But when I called the routine within a tight loop (separated only by the cycles needed to print the values on the console) I found that two retrievals within a short period of time often simply returned the same value. As as example, in 100 times through the loop, the output was 2 instances of 111, 82 of 112, and 16 of 113. So if I wanted a full 16 bit seed, I would probably massage the low order byte (add something to it? rotate it?) and stuff it into H rather than access the R register a second time. But for the limited purpose of game startup, I'm not sure that would be necessary.

Steve Mitchell

Douglas Miller <durgadas311@gmail.com> wrote:

>Russell Marks wrote:
>>... And it even gives you a way of checking whether interrupts were
>> previously enabled or not in e.g. an NMI handler.
[...]
> The Z80 CPU already does this for NMI, as long as you use RETN to
> return from the NMI handler.

Ah, but what if you don't return because the hardware uses the NMI to
implement a soft power-off button? I actually used this one in ZCN (in
src/powrhndl.z), which is why I mentioned it. :-)

-Rus.

On Saturday, August 5, 2023 at 4:01:24 PM UTC-5, Russell Marks wrote:
> Ah, but what if you don't return because the hardware uses the NMI to
> implement a soft power-off button? I actually used this one in ZCN (in
> src/powrhndl.z), which is why I mentioned it. :-)
>
> -Rus.

If you're powering off, do you care if interrupts were enabled or not? If your handler doesn't power off, then why shouldn't it use RETN?

Douglas Miller <durgadas311@gmail.com> wrote:

>Russell Marks wrote:
>> Ah, but what if you don't return because the hardware uses the NMI to
>> implement a soft power-off button? I actually used this one in ZCN (in
>> src/powrhndl.z), which is why I mentioned it. :-)
[...]
> If you're powering off, do you care if interrupts were enabled or
> not?

In this case yes, because on the Amstrad NC100 (the hardware I'm
talking about) the NMI handler will optionally save context for
powering back on; in ZCN it always does. And it could e.g. have
interrupted a normal interrupt handler. It gets fun when you can have
an NMI interrupting a serial interrupt interrupting a 100Hz timer
interrupt, which was one of the crazier things I bothered to support
(perhaps even correctly).

-Rus.

Intending to test the the quality of the XorShift algorithm, I wrote the following TESTRAND program, to be executed as:

>TESTRAND N

(N = 1...9)
-------------
(here, the source in pseudo-assembler...)

Hits: defs 8000H

start:

call xrndseed

Init Hits buffer to zero

repeat N times
repeat 8000H times
call xrnd ;returns HL
ld de,Hits ;increment Hits[HL]
add hl,de
inc (hl)
end
end

type the Hits vector values, in ASCII, (lines of 64 chars)
-------------

Results show that XorShift works perfectly:

>TESTRAND 1
1002202001101111202111111112000001102222202121211221200101100220
0001200222221012100021121112110200211212011211011122120112112020
....
1011012111121111102121210002110201102110101011111120121010001011
1121121221211210211212102002221121201212222212200001012201101112
>TESTRAND 2
1222222222222222222222222222222222222222222222222222222222222222
2222222222222222222222222222222222222222222222222222222222222222
2222222222222222222222222222222222222222222222222222222222222222
.... (all lines identical)
2222222222222222222222222222222222222222222222222222222222222222
2222222222222222222222222222222222222222222222222222222222222222
>TESTRAND 4
2444444444444444444444444444444444444444444444444444444444444444
4444444444444444444444444444444444444444444444444444444444444444
.... (all lines identical)
4444444444444444444444444444444444444444444444444444444444444444
4444444444444444444444444444444444444444444444444444444444444444
>TESTRAND 8
4888888888888888888888888888888888888888888888888888888888888888
8888888888888888888888888888888888888888888888888888888888888888
.... (all lines identical)
8888888888888888888888888888888888888888888888888888888888888888
8888888888888888888888888888888888888888888888888888888888888888
>

I hope this test shows without a doubt the quality of the XorShift algorithm...

Those results look suspiciously "perfect" (aside from the anomaly for value "0"). If I run a similar test on Java in Linux (which might be using the Linux rand number generator, but either way should be a very good one), I do not get "perfect" distribution. I suspect your xrnd routine is "running out of steam" and failing to produce randomness after a while (might be degenerating into just plain counting).

The program I'm using is:
-----------------------------------------------
import java.util.Random;

public class rand {
Random random;
byte[] Hits;

public rand(int N) {
random = new Random();
Hits = new byte[32768];

for (int x = 0; x < N; ++x) {
for (int y = 0; y < Hits.length; ++y) {
int r = random.nextInt() & 0x7fff;
++Hits[r];
}
}
for (int y = 0; y < Hits.length; ++y) {
System.out.format("%c", Hits[y] < 10 ? '0' + Hits[y] : 'v');
}
System.out.format("\n");
}

public static void main(String[] args) {
if (args.length != 1) {
System.err.format("Usage: rand N\n");
System.exit(1);
}
int N = Integer.valueOf(args[0]);
new rand(N);
}
} ------------------------------------------------
And I get output for "4" that is:
========================3351634325624331v75415332342238737447335455318451633342647445631
4423334933342434875548514462423321263353335322556521453624323433
....
36115454617525457137144696443414252112321663v17336v3343722246112
43845205472v2553124866443223241734214236412344653433414645235353
========================(the 'v' characters indicate a count greater than 9)

Pe duminică, 6 august 2023, la 15:36:07 UTC+3, Douglas Miller a scris:
> Those results look suspiciously "perfect" (aside from the anomaly for value "0"). If I run a similar test on Java in Linux (which might be using the Linux rand number generator, but either way should be a very good one), I do not get "perfect" distribution. I suspect your xrnd routine is "running out of steam" and failing to produce randomness after a while (might be degenerating into just plain counting).
>
> The program I'm using is:
> -----------------------------------------------
> import java.util.Random;
>
> public class rand {
> Random random;
> byte[] Hits;
>
> public rand(int N) {
> random = new Random();
> Hits = new byte[32768];
>
> for (int x = 0; x < N; ++x) {
> for (int y = 0; y < Hits.length; ++y) {
> int r = random.nextInt() & 0x7fff;
> ++Hits[r];
> }
> }
> for (int y = 0; y < Hits.length; ++y) {
> System.out.format("%c", Hits[y] < 10 ? '0' + Hits[y] : 'v');
> }
> System.out.format("\n");
> }
>
> public static void main(String[] args) {
> if (args.length != 1) {
> System.err.format("Usage: rand N\n");
> System.exit(1);
> }
> int N = Integer.valueOf(args[0]);
> new rand(N);
> }
> }
> ------------------------------------------------
> And I get output for "4" that is:
> =========================
> 3351634325624331v75415332342238737447335455318451633342647445631
> 4423334933342434875548514462423321263353335322556521453624323433
> ...
> 36115454617525457137144696443414252112321663v17336v3343722246112
> 43845205472v2553124866443223241734214236412344653433414645235353
> =========================
> (the 'v' characters indicate a count greater than 9)

Well, the explanation is simple: XorShift "produces" series of 64K-periodical values, all different ! That's why, when repeating calling xrnd a multiple of 64K times (N), all 64K hits are equal to N.

The 0 'anomaly' in my test is also a banal case: XorShift avoids returning 0, and my xrnd returns only positive numbers, by setting bit 7 = 0, therefore all (signed) integers > 32K are returned as (unsigned) integers with 'sign' bit set to 0! (e.g. 8000H is 'transformed' to 0)

BDS-C had a pretty good pseudo-random number generator, although it uses a 32-bit seed. Code is pretty simple:
-----------------------------------
FUNCTION rand
lhld rseed
xchg
mvi a,48h
ana e
jz rand1
jpe rand1
stc
rand1: lhld rseed+2
mov a,h
ral
mov h,a
mov a,l
ral
mov l,a
shld rseed+2
mov a,d
ral
mov h,a
mov a,e
ral
mov l,a
shld rseed
mov a,h
ani 7fh
mov h,a
ret
ENDFUNC
-----------------------------------------
This returns a 15-bit pseudo-random number. The distribution test shows a pattern much more like modern random number generators. It does require, or at least should have, a 32-bit seed.

Pe duminică, 6 august 2023, la 16:46:31 UTC+3, Douglas Miller a scris:
> BDS-C had a pretty good pseudo-random number generator, although it uses a 32-bit seed. Code is pretty simple:
> -----------------------------------
> FUNCTION rand
> lhld rseed
> xchg
> mvi a,48h
> ana e
> jz rand1
> jpe rand1
> stc
> rand1: lhld rseed+2
> mov a,h
> ral
> mov h,a
> mov a,l
> ral
> mov l,a
> shld rseed+2
> mov a,d
> ral
> mov h,a
> mov a,e
> ral
> mov l,a
> shld rseed
> mov a,h
> ani 7fh
> mov h,a
> ret
> ENDFUNC
> -----------------------------------------
> This returns a 15-bit pseudo-random number. The distribution test shows a pattern much more like modern random number generators. It does require, or at least should have, a 32-bit seed.

I made the same test, using this BDS-C routine.

Results:

>TESTRAND 1
1020101220114220102203121331212010001132111300211120421220021213
1010010010010110110130210010020203100000011310310302000111203012
....
2020120300101122113102301112001122000020103310122011101001013101
0112100110000000110014311000001102010010013000001100110011002000

>TESTRAND 2
7423433323222134003004031301302220324010132510142320017321422352
6204431313113112311341241312414533021422212316272121211215322745
....
2312341400102124231243122110022332451222200511150021327025343214
1141002431210122121202010004520133151203131232112431213032133332

>TESTRAND 4
4435626428555933229446728168192441475652285523442443555452383238
3311436332533536532517153454234536527244943773415516357161577555
....
2481372424152342354214722426571458354051633353325363312333275238
613464233656126473536320273561433251224:421346725356524437356553

>TESTRAND 8
74667988779@988856:596=5;6788:67:88786;9:<9:4=7679:469696778>549
6:4<;797>;985<1<7;6:<4896469;467<88>76765765666;484;5<6=;:7546@8
....
6:=69<48::8877778776766877:9:579>8796:9:>6688<4778778:778776=7;;
7:54<88758757777><?:86=79::5=46>866458:489<8;4759:7@9?667985:648
(here, chars different to digits represent values > 9)

ladislau szilagyi <ladislau_szilagyi@euroqst.ro> wrote:

> Intending to test the the quality of the XorShift algorithm, I wrote
> the following TESTRAND program
[...]
> I hope this test shows without a doubt the quality of the XorShift
> algorithm...

I won't claim to be an expert on this stuff, but I get the impression
that testing RNGs is really quite hard to do well.

-Rus.

Hi,

below is a small test for my XorShift random numbers generator:

:20010000ED7B0100CD6001CD2402218401CD6F01010000CD0D02C5CB3CCB1DCB3CCB1DCB27
:200120003DCB3DCDD9010E2ACD8101CD7B01B72817CD7E01FE03CA00002AD7017DFE012850
:2001400007CB3CCB1D22D701ED4BD7010B78B120FBC10B78B120BC210020CDD901C30000D4
:200160002A0100232323117B01010900EDB0C97EB7C8234FE5CD8101E118F4C30000C300D8
:2001800000C300001B5B324A1B5B480011D30121CE013AD20106004F09477E122B1310FA8D
:2001A000AF12C9FD21CF0116001E000608B7CB15CB137BD60A3F30015F10F3CB157BC63092
:2001C000FD7700FD23147DB720DF7A32D201C91A1A1A1A1A1A1A1A0080E50E1BCD81010E41
:2001E0005BCD8101E1E57C3C6FCDA301CD8C0121D301CD6F010E3BCD8101E12CCDA301CD88
:200200008C0121D301CD6F010E48C381012101007C1F7D1FAC677D1F7C1FAD6FAC67220E82
:2002200002CBBCC9ED5F6FED5F67B5200123220E02C91A1A1A1A1A1A1A1A1A1A1A1A1A1A9E
:200240001A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A5E
:200260001A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A3E
:00000001FF

It needs a VT100 screen with size at least 64 cols x 32 rows.

The test clears the screen and keeps typing 64K 'star' characters at coordinates returned by
repeteadly calling xrnd.

The coordinates are calculated using the following rule:

row = (bit 14 ... bit 10) from xrnd
col = (bit 9... bit 4) from xrnd
(bit 3...bit 0) are dumped

You can speed-up the test hitting ( repeateadly ) any key; CTRL C terminates the test.

Of course, the final screen looks like a full 64 x 32 rectangle of 'stars' , but (at least in the initial phase)
it is interesting to observe how the 'stars' spread out on the screen; this can give you an interesting
visual representation on how the random number generator works.

If you run the test at full speed (press any key in auto-repeat mode, in the first seconds...),
it will take aprox. one minute to finish, for a 7MHz Z80 machine .

The 64 x 32 rectangle gets filled quickly, but keep in mind that each 'cell' is overwritten 16 times...

Ladislau