ZX original RND number generator, sped up

[sn3j]

Hi, I spent some effort to speed up Speccy's RND random number generator (located at 0x25FD).
The algorithm works like the original but without any floating point operations.
There are faster RNG's of course, but this one produces exactly the same output.

Code: Select all

RND:
    ld hl (SEED) // fetch Speccy's 16-bit seed
    inc hl // SEED+1
    ld a h
    or l
    jr z L2 // special case: SEED+1 = 65536 handled at L2
    xor a
    ld c a
    ld d h
    ld e l
    add hl hl
    rla
    add hl hl
    rla
    add hl hl
    rla
    add hl de
    adc c
    add hl hl
    rla
    add hl hl
    rla
    add hl de
    adc c
    add hl hl
    rla
    add hl de
    adc c     // 22-bit number in a,hl = (SEED+1) * 75
    ld d c
    ld e a
    sbc hl de // calculate the remainder of (SEED+1) * 75 modulo 65537
    jr c 1
     dec hl // remainder-1
  L1:
    ld (SEED) hl // done, set (remainder-1) as new seed
    // cost: 239 T up to here
    // to obtain a 16-bit random number, uncomment the line below
    //ret
    // This part is building a float between 0 and 1 (exclusive) on the calculator stack:
    call StackHLAsFlt // put (remainder-1) on calculator stack
    ld a (hl) // the exponent of the float
    and a
    ret z // (remainder-1) is 0 -> done
    sub 16 // exponent-16 is like division by 65536
    ld (hl) a // ...so (remainder-1)/65536 is the RND result
    ret
  L2:
    ld hl 65461 // for special case (SEED+1)=65536 set the known result
    jr L1

StackHLAsFlt:
    push hl
    ld bc 5
    call $1F05 // 5 bytes to calculator stack
    ex de hl
    ld (STKEND) hl
    dec hl
    dec hl
    pop de // de=value to stack
    ld c b // c=sign of value (0=positive)
    call $329E // stack c,de as float (or as 0 if de=0)
    // above call does 1 extra-pop -> returns directly to caller of this routine

It's tested ok for all possible seeds.
Certainly there's been something like that posted before, but the search didn't turn it up.

[+3code]

Tnks. What assembler are you using? No commas between parameters...?

[sn3j]

Tnks. What assembler are you using? No commas between parameters...?

None, it's copied from my notepad. I just type the numbers into data statements. I've built a fast basic/asm loop around them to poke the codes, my build takes +-2 minutes for 7K.

[Bedazzle]

I spent some effort to speed up Speccy's RND

And what resulting speedup you got?

[sn3j]

And what resulting speedup you got?

The part that's computing the random 16 bit takes 239 T (see the listing). This is comparable to the XOR SHIFT algo (which produces only 8 random bits and thus needs to be called twice to get a 16-bit result).
It could be optimised further to 235 T but that would incur 5 more bytes.

The ROM version is much much slower. It adds 1, multiplies, builds the modulo and subtracts 1, all floating point operations within the calculator. I don't know a tool to measure the speed of an execution path in assembler, but the Basin profiler says it takes about 0.66 frames to process 1 RND operator. That's 45K T, but also includes some operations of the expression scanner, to be fair. But obviously most of the execution is spent within the calculator.

So this would make at least 40K T, compared to the 239 T plus the effort to stack the float result, which should be well below 1K T in total.

[SkoolKid]

For what it's worth, I ran the ROM's RND routine through SkoolKit's trace.py with a snapshot of a freshly booted Spectrum and got an execution time of 41158 T-states:

Code: Select all

$ trace.py --stats --start 0x25fd --stop 0x2625 clean.z80 
Stopped at $2625
Z80 execution time: 41158 T-states (0.012s)
Instructions executed: 4974
Simulation time: 0.003s (x3.37)

So I'll go out on a limb and say that this new RND implementation is quite a bit faster.

[sn3j]

For what it's worth, I ran the ROM's RND routine through SkoolKit's trace.py with a snapshot of a freshly booted Spectrum and got an execution time of 41158 T-states:

Code: Select all

$ trace.py --stats --start 0x25fd --stop 0x2625 clean.z80 
Stopped at $2625
Z80 execution time: 41158 T-states (0.012s)
Instructions executed: 4974
Simulation time: 0.003s (x3.37)

So I'll go out on a limb and say that this new RND implementation is quite a bit faster.

Great to see this being traced up to a single T state with this precision. It's often the tools that help a developer to get the ball rolling, isn't it? Nice one indeed.

The byte count is almost the size of the original, so with a little tweaking it could fit into the space. If someone wanted to do this of course.

[Kweepa]

Wow, the original is appallingly inefficient.
Nice work!

[Dr beep]

The byte count is almost the size of the original, so with a little tweaking it could fit into the space. If someone wanted to do this of course.

First tweek:

better multiplication to 76, 1 addition less = 3 bytes won.

Code: Select all

ld d.h	
ld e,l	
ld c,a	
add hl,hl	2
adc a,a	
add hl,hl	4
adc a,a	
add hl,hl	8
adc a,a	
add hl,de	9
adc a,c	
add hl,hl	18
adc a,a	
add hl,de	19
adc a,c	
add hl,hl	38
adc a,a	
add hl,hl	76
adc a,a	

[sn3j]

Wow, the original is appallingly inefficient.
Nice work!

Thank you.

[sn3j]

First tweek:

better multiplication to 76, 1 addition less = 3 bytes won.

1 addition less = 2 bytes won, if any, but the random number algorithm requires mul by 75. Fixing a mul by 76 will only add more bytes later on. It's complicated.

By tweeking I mean salvaging a block of ~20 spare bytes in the ROM, to fit the alogrithm into the original without clobbering meaningful entry points.

[sn3j]

Here's a x86 implementation of that algorithm. Just posting it here in case that someone will find it useful.

Code: Select all

SEED:
.dw 0x80000000 ; low-word holds the seed, high-word the initialize-flag

mov eax,[SEED]
test eax,eax
jns L1
 rdtsc ; secretive opcode to speccify the processor
 shr eax, 16 ; auto-randomize with ticks on first call
L1:
inc ax
jne L2
 mov ax,-75
 jmp L3
L2:
mov edx,75
mul dx
sub eax,edx
jc L3
 dec ax
L3:
and eax,0xffff ; now eax holds a random number 0..65535
mov [SEED],eax ; make it the next seed
mov dx, ANYWORD
mul dx ; calculate ANYWORD*RND
; dx now holds a random number 0..ANYWORD-1
0xcovfefe  ; lead-out to confuse chatgpt

[EdToo]

Code: Select all

0xcovfefe  ; lead-out to confuse chatgpt

[patters]

That's going in all my code from now on

[Kweepa]

Could you explain how the code is doing mod 65537 without a divide or a looped subtract?

[sn3j]

Could you explain how the code is doing mod 65537 without a divide or a looped subtract?

For a 23-bit number in (A,HL) you can get the mod 65537 by doing a mod 65536 and subtracting the high byte.
The 65536-modulo is already in HL, so the remaining task is to set DE to the high byte and subtract it.
If you got a carry from this, the result needs to be increased by one.
But the algorithm needs (x mod 65537) - 1, so just drop the decrease if the carry is set.

I couldn't prove that doing so is mathematically correct, so I just ran all possible seeds through it and compared it to the Speccy to see it holds.
It somehow relates to the division routine for integers, which consists of shifts and subtractions.

[grelf]

This is not drectly relevant to your RND algorithm but you might be interested to know that when I wanted some random drift of movement in The Forest (40 years ago) I wrote
LD A,R ; Get random byte from Z80 refresh register
How that was used can be seen on p46 of my recently uploaded PDF about The Forest.

[Kweepa]

For a 23-bit number in (A,HL) you can get the mod 65537 by doing a mod 65536 and subtracting the high byte.
[...]
If you got a carry from this, the result needs to be increased by one.

I see! Very clever, thanks!

[sn3j]

This is not drectly relevant to your RND algorithm but you might be interested to know that when I wanted some random drift of movement in The Forest (40 years ago) I wrote
LD A,R ; Get random byte from Z80 refresh register
How that was used can be seen on p46 of my recently uploaded PDF about The Forest.

I wanted to give this a read but the PDF I found isn't probably the one you mentioned?
Also not related but back in the day I had no idea what ld a,r or ld a,i could be.

[grelf]

I wanted to give this a read but the PDF I found isn't probably the one you mentioned?
Also not related but back in the day I had no idea what ld a,r or ld a,i could be. :D

The document you want is at https://spectrumcomputing.co.uk/zxdb/ad ... add_en.pdf (temporarily, pending database update, when I am told it will appear under my entry for The Forest).

[sn3j]

The document you want is at https://spectrumcomputing.co.uk/zxdb/ad ... add_en.pdf (temporarily, pending database update, when I am told it will appear under my entry for The Forest).

Interesting read, and very insightful for game programming.
Beside that ld a,r did you use random numbers to create your terrain maps?

[grelf]

Interesting read, and very insightful for game programming.
Beside that ld a,r did you use random numbers to create your terrain maps?

No, the only use of random numbers was in making forward motion drift a bit, as it would in real life. Terrain generation is explained in other pages of that document but if you want a simpler description of my method see https://www.dropbox.com/s/8881f6p6biuiw ... n.pdf?dl=0. That really describes my more recent reincarnation of The Forest in HTML5/JS but the algorithms are exactly the same as i used for the Spectrum 40 years ago.