Improved RNG for Pikobrain

[Hanzlu]

This is about a "simple and effective" way of creating random numbers

Pikobrain has a random number generator (RNG). I thought it was creating actual random numbers, but it wasn't.
I noticed this when I made a program, that would go line by line on the screen. If the random number was divisible by <x>, a red pixel would be drawn. However, the image that program made was patterned. Like this:



This meant the RNG got into loops of numbers, such that these patterns would occur.
So, I sat down all evening, tinkering with various combinations of arithmetic and bitwise operations, with no success.
At least until by about 11pm, when it suddenly drew something like this:



As far as I am/was able to tell, that image has no patterns. The code that was creating this was also just the same kind of type I had tinkered around with all evening, but it just worked. It was also really simple, I'll show it soon.

Since then I have also made programs to test the nature of the new RNG.
The RNG does create patterns sometimes, but most of the time the image seems quite random.
I've printed random values, and I have been unable to find patterns when printing 512 random numbers in a row.
I also made a program that created two random numbers, and then checked how many random numbers later until those two random numbers appeared again. That doesn't really mean a pattern is found, since it could also be just by random. But it almost always took several thousand random numbers until the same two would appear again.
This is to say that the RNG is effective enough.

So, this is the code for it:

Code: Select all

random:
    ;random number generator
    push cx ;store for assembly macros
    push dx
    mov ah, 0h ;get tick
    int 1ah
    mov ax, RANDOM_BUFFER
    mov fs, ax
    xor si, si
    mov ax, [fs:si]
    sub ah, dl ;update number = generate
    sub al, ah ;al is random number returned
    rol ax, 1h
    mov [fs:si], ax ;store
    pop dx
    pop cx
    ret

When I first made a RNG, I thought I could just use the ah=0 int 1ah call to get the tick. However, since the tick only increases once every 1/18.2 seconds it's a useless method for creating 1000s of numbers quickly.
So then I made something that is similar to what I have now, that would:

Code: Select all

sub ah, dl
sub al, ah

Since I knew that just adding a certain number is pretty useless for RNG, I thought changing that number (ah), would be able to alter al enough in the long run to make it random. But as we could see from the first image, that was not the case.
Eventually I removed some lines of code that dealt with if al==0 and used the rol ax, 1h : and it worked.

That's not well explained, but. I'll explain the new RNG:
It calls a BIOS function that returns the current tick. I use the byte in dl, that is increased ~18.2 times a second.
(By using that number I essentially get a "random" number when making the first random number)
I then subtract that from ah, which is subtracted from al (which is the random number "returned").
Then somehow, rotating ax by one step does magic, that causes the whole thing to be quite "random".
RANDOM_BUFFER (using fs:si) is simply were the random number will be stored, such that it can be updated the next time the RNG is called.

---
Many of the RNGs I looked at yesterday requires a lot of calculations. I tried using the classic "Linear Congruential" method, which is simple, but I found no good combination of numbers for 16-bit assembly.
So, I would call the method I ended up with yesterday small and effective in providing random bytes. It also seems as if ah is "random", so ax as a whole can be used as a random number.

[nullplan]

Many of the RNGs I looked at yesterday requires a lot of calculations. I tried using the classic "Linear Congruential" method, which is simple, but I found no good combination of numbers for 16-bit assembly.

Erm, you are using FS, so you are requiring a 386 at least, so you do have 32-bit registers available. You could just use musl's random function:

Code: Select all

#include <stdlib.h>
#include <stdint.h>

static uint64_t seed;

void srand(unsigned s)
{
	seed = s-1;
}

int rand(void)
{
	seed = 6364136223846793005ULL*seed + 1;
	return seed>>33;
}

Or, in assembler:

Code: Select all

RANDOM_SEED: dq 0
; ...
srand: ; argument in eax
  dec eax
  mov eax, [RANDOM_SEED]
  mov dword 0, [RANDOM_SEED + 4]
  ret
align 8
multiplier: dq 6364136223846793005
rand:
  ; 64-bit multiplication on 32-bit machine:
  ; res = (a_hi * 2^32 + a_lo) * (b_hi * 2^32 + b_lo) = (a_hi b_hi 2^64 + a_hi b_lo 2^32 + a_lo b_hi 2^32 + a_lo b_lo)
  ; first term is overflow, and therefore discarded
  ; res_hi = a_hi b_lo + a_lo b_hi + hi(a_lo b_lo)
  ; res_lo = lo(a_lo b_lo)
  push bp
  mov bp, sp
  sub sp, 8 ; need scratch space
  mov eax, [RANDOM_SEED]
  mul dword [multiplier]
  mov [bp-8], eax
  mov [bp-4], edx
  mov eax,[multiplier+4]
  mul dword [RANDOM_SEED]
  add [bp-4], eax
  mov eax,[multiplier]
  mul dword [RANDOM_SEED + 4]
  add eax, [bp-4]
  mov [RANDOM_SEED+4], eax
  mov edx, [bp-8]
  mov [RANDOM_SEED], edx
  shr eax
  add sp, 8
  pop bp
  ret

See, not that complicated.

It calls a BIOS function that returns the current tick. I use the byte in dl, that is increased ~18.2 times a second.
(By using that number I essentially get a "random" number when making the first random number)
I then subtract that from ah, which is subtracted from al (which is the random number "returned").

18Hz is not that fast compared to a multi-GHz processor. If you call it often in quick succession, you will always get the same time stamp. So, arithmetically, what is going on so far? You have some 16-bit number "seed", and some 8 bit number "ticks". The first subtraction means the same as "seed -= 256 * ticks". The second sub means roughly "seed -= seed / 256". Not exactly, because no carry into the high byte is happening, but this is as close as I want to get.

So we have

Code: Select all

seed' = (seed - ticks * 256) - ((seed - ticks * 256) / 256)
  = seed - ticks * 256 - seed / 256 + ticks
  = 255/256 seed - 255 ticks

As I said, not exactly. But mostly, what this means is that you are subtracting a multiple of the ticks value each time the RNG is called. If you call it fast enough, the ticks value is going to be constant, meaning this is exactly a linear congruential generator with all the well-known weaknesses of such, and a completely unproven multiplier. The only spin on things is your rotation now. I don't know enough maths to be able to understand a rotation as arithmetic (it would be some weird formula with branch cuts), so I cannot analyze that.

[eekee]

Good test!

As far as I know, linear PRNGs require you to throw away the first N results because they're hardly random. N can be over 50, or even several hundred for a large-pool Mersenne Twister, if I remember right. Looking at your image, I may have underestimated. If you're interested, the following PDF link is specifically about the Mersenne Twister, but has things to say about lots of different PRNG types. I plan to use a xorshift, but it looks like you've found a good one.
https://arxiv.org/pdf/1910.06437.pdf

[Hanzlu]

I have somewhat recognized that I am able to use 32-bit operations and registers since I do utilize fs and gs, all of which introduced with the i386.
However, since I am making a 16-bit OS I decided I should avoid doing so.
Two other things also keep me from utilizing existing models. I wish for Pikobrain to be small and made by myself. Which I guess is the goal for most of us, but we draw different lines.

nullplan's simplification about my method of RNG is quite interesting, I hadn't thought of using math to create the formula.

Code: Select all

seed = 255/256 seed - 255 tick

seems to be the formula of the old RNG I used. But adding the rotate and removing some other stuff I had, did give it a "spin".
It is true that with a really fast processor my RNG could turn out a bit bad. But with the ~1.8 GHz stuff I have it, and the simple stuff I'd use a RNG for, it is sufficient.
Actually. What kind of situations do you need to randomize huge amounts (millions) of random numbers quickly for?

It may be true as eekee said that the first couple numbers are not that random. That may be something to think about.
Thanks for that pdf, I'll take a look at it.

[Octocontrabass]

Then somehow, rotating ax by one step does magic, that causes the whole thing to be quite "random".

Unless you stumble across particular combinations of seed and tick that cause short loops in the output. It's worst when seed and tick are both 0: the output is always 0. I've also managed to find combinations that cause repeating cycles of 16 or 31 values, and I've found combinations that repeat over much longer periods but contain shorter cycles of 32 values split about evenly between repeats from the previous cycle and values that differ in only one bit.

So, that might be a problem depending on how often you need a random number.

[Hanzlu]

Unless you stumble across particular combinations of seed and tick that cause short loops in the output. It's worst when seed and tick are both 0: the output is always 0. I've also managed to find combinations that cause repeating cycles of 16 or 31 values, and I've found combinations that repeat over much longer periods but contain shorter cycles of 32 values split about evenly between repeats from the previous cycle and values that differ in only one bit.

So, that might be a problem depending on how often you need a random number.

It is true that having 0 as seed and tick is really bad, and it can occur.
I also just removed a piece of code that always set the seed to 0 when a program is done running. Meaning that whenever a new program started the seed was 0. Now that is no longer the case, and the last seed of program A, will be used as seed when starting program B.

Octocontrabass seem to have tested values of the RNG and spotted that it gets into bad cycles, at least occasionally.
I did do some simple testing myself yesterday, where I made sure all values are equally likely, that the average length between r and r+1 is 0x80, and a little on how likely a certain digit was. On a "non-patterned" sample those test returned values I was happy with.
Are there any good programs for testing RNGs?

This morning, I have also drawn more images to spot how often patterns will be noticeable. Sometimes they are easy to spot, sometimes quite hard, meaning that I may miss them. An image should make about 128k pixels. Out of 20 images 6 had patterns. Typically patterns do not cover more than half the image, so probability would then be 6/(2*14) ~=21%, which is not great. However, typically patterns still make a few hundred numbers before "restarting", so it's ok for making a 16*16 board for example.

The tightest pattern I found was this:


There the length between patterns is just above 16.

[klange]

I use this classic xorshift, which is very robust: https://github.com/klange/toaruos/blob/ ... lib/rand.c

Code: Select all

static uint32_t x = 123456789;
static uint32_t y = 362436069;
static uint32_t z = 521288629;
static uint32_t w = 88675123;

int rand(void) {
	uint32_t t;

	t = x ^ (x << 11);
	x = y; y = z; z = w;
	w = w ^ (w >> 19) ^ t ^ (t >> 8);

	return (w & RAND_MAX);
}

A version of this has been in my kernel and later libc for most of the life of ToaruOS.

[eekee]

Thanks klange, I've ported it to pforth to replace an exceedingly simple 16-bit prng.

[Hanzlu]

Alright. Now I've been able to utilize the new RNG to make a text based minesweeper game without patterns made by the mines:



I use the arrow keys to select which square to "open", and then it will show a number or an empty square.
I can mark squares I think are mines with * and eventually finish a session like above.
Due to the oversimplified way I check how many mines are around a certain square, it can cause squares on the edges to show "wrong" numbers, although they actually point to mines on other lines or outside the board.

But it was nice to see that the RNG seems to be working and to code a game in Pikoasm on the system itself.