Programming the 80’s way #4
Random Numbers in 16 bits
The ZX Spectrum Next’s manual explains in Chapter 11 how random numbers generator works.
There is a useful disassembly (https://skoolkid.github.io/rom/dec/asm/9720.html) about the standard ROM routine, that using the “ROM calculator” in short uses the following formula
NEXT_SEED := ( ( 75 * ( SEED + 1 ) ) % 65537 ) – 1
where % is the “modulo operator”.
So starting with any SEED between 0 and 65535, the NEW_SEED is always between 0 and 65535, and the series that emerges is a fairly random sequence of integers that repeats itself after 65536 iterations.
Spectrum’s RND function simply returns NEW_SEED divided by 65536.
Since a number larger than 65536 is involved (i.e. modulo base 65537), and Spectrum’s Forth usually provides only quotient/remainder routine that can divide a 32-bits integer giving a 16-bits integer result and a 16-bits remainder, for a long time I deemed impossible performing such an operation without “large divisor” quotient/remainder routine. And, this meant that it was impossible in my vForth too.
In this post, I show a clever achievement that circumvents the classic 16-bits limitation, in this case.
First of all, since Forth provides words that can handle 32-bits numbers addition and subtraction, I thought that I could “emulate” a quotient/remainder routine by “repeated subtractions”, and that was a fairly right path.
Immediately I saw that sutracting 65537 from a 32-bit integer, i.e. $10001 in hexadecimal, was roughly equivalent to decrement both higher and lower 16-bits parts of it,
and that the reminder was simply some kind of “difference” between these two parts.
This was a good start, since instead of performing some huge division I just had to subtract two integers, and if the subtraction gave a negative number I just had to re-add 65537 to have it positive again.
Then I had to resolve these two limit conditions inherent using 16-bits integer Arithmetics :
1. when SEED is 65535, the first inner addition +1 produces a ZERO instead of a 65536 giving a wrong result.
2. 65537 is equivalent to 1.
So I exploited the following Forth final optimized definition that I listed below.
Here is a few seconds video (https://youtu.be/4Wh7r0ZHbSY) that shows how fast this routine is and how fast we can plot 65536 pixels using LAYER 1,2 graphics-mode.
decimal 23670 constant SEED
: next_seed ( n1 — n2 )
75 UM* 2dup U< if – else – 1- then
-75 \ = 65461
needs graphics layer12
256 0 do
256 0 do
SEED @ next_seed SEED !
SEED @ 9 rshift 24 + SEED @ 511 and plot
Leave a Reply