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 )
  1+ ?dup
  if
    75 UM* 2dup U< if – else – 1- then
  else
   -75 \ = 65461
  then
;

needs graphics layer12

: tester
  256 0 do
    256 0 do
      SEED @ next_seed SEED !
      SEED @ 9 rshift 24 + SEED @ 511 and plot
    loop
  loop
;

cls tester

_M.