[Tack-devel] random numbers and time zones

[George K. <ke...@gm...>]

I write about random numbers in the Amsterdam Compiler Kit, then about
time zones.

ack comes with an example in several languages of the game, "See if
you can guess my number." The Basic version in examples/hilo.bas is
easy, because the computer's number is always zero, so I always guess
0 and win in 1 try.

The code to pick the number is
    1010 Number% = rnd(1) mod 100

ACK's EM-Basic ignores the 1 in rnd(1); Microsoft's QBasic would check
if the 1 is positive. Then, in both EM-Basic and QBasic, RND should
return the next random number as a float from 0.0 to 1.0. The MOD in
`rnd(1) mod 100` is an integer operation, so Basic rounds the float to
an integer 0 or 1. Then the result of 0 mod 100 or 1 mod 100 is 0 or
1. The game should pick 0 or 1.

EM-Basic calls C's rand(), but uses the wrong maximum for rand() on
platforms with 4-byte int. This causes RND to always pick numbers
close to 0. Then the game always rounds the numbers to 0.

There are two random number generators in ack.

C's rand() uses the linear congruential generator
    next = next * 1103515245 + 12345;
rand() discards the lowest 16 bits,
and returns the next 15 bits of that value.

Modula-2's random uses an additive generator
    x[k] = x[k - 55] + x[k - 24]
but x is a ring buffer of the last 55 values.

Both are from the 1980s. I might try to replace them with a more
recent generator.

Two recent algorithms are
xoroshiro128+ from http://xoroshiro.di.unimi.it/
PCG from http://www.pcg-random.org/

I didn't like xoroshiro128+ because it uses 64-bit integers, and ack
lacks 64-bit operations. It only uses bit operations (xor, shift,
rotate) and one can easily split them into 32-bit operations, but I
didn't want to try.

I didn't like PCG because it uses multiplication, which is slow in
processors without a multiply instruction, like the i80.

I am now looking at
sfc32 from http://pracrand.sourceforge.net/

sfc32 uses 32-bit integers with bit operations and addition. Modula-2
seems to have no bit operations on integers (both shifts and bitwise
logic), but I might write the code in EM. sfc32 has a rotate (barrel
shift) and EM code can rotate with ROL or ROR. C code would split the
rotate into shifts and bit-or, and ack can't optimize it to ROL or
ROR. Back end for PowerPC can't compile ROL or ROR, but I might teach
it.

QBasic by tradition uses
    randomize timer
to seed the generator.

EM-Basic has randomize but is missing timer, to return a float
counting seconds since midnight. One would need to know the time zone
to calculate midnight. That's a problem because ack's libc can't find
the time zone. It wants to call ftime() to get the time zone from the
kernel, but that technique is obsolete. If I try to call ctime(), the
compile fails as the linker can't find ftime().

The modern way is to open /etc/localtime and read tzfile(5) for time
zone, but ack's libc hasn't learned to do that. Also, libc has an
outdated default rule for summer time. It doesn't know that the
European Union changed the rule in 1996.

--George Koehler