OSDev.org

The Place to Start for Operating System Developers
It is currently Sat Oct 23, 2021 1:02 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 9 posts ] 
Author Message
 Post subject: Improved RNG for Pikobrain
PostPosted: Tue Sep 14, 2021 5:07 am 
Offline
User avatar

Joined: Sun Mar 28, 2021 7:46 am
Posts: 9
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:

Image

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:

Image

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:
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:
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.

_________________
https://www.github.com/hanzlu/pikobrain


Top
 Profile  
 
 Post subject: Re: Improved RNG for Pikobrain
PostPosted: Tue Sep 14, 2021 9:34 am 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 1111
Hanzlu wrote:
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:
#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:
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.

Hanzlu wrote:
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:
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.

_________________
Thou hast outraged, not insulted me, sir; but for that I ask thee not to beware of Starbuck; thou wouldst but laugh; but let Ahab beware of Ahab; beware of thyself, old man.


Top
 Profile  
 
 Post subject: Re: Improved RNG for Pikobrain
PostPosted: Tue Sep 14, 2021 10:07 am 
Offline
Member
Member
User avatar

Joined: Mon May 22, 2017 5:56 am
Posts: 586
Location: Flying strange spaceplanes in a distant solar system
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

_________________
Pixel Forth


Top
 Profile  
 
 Post subject: Re: Improved RNG for Pikobrain
PostPosted: Tue Sep 14, 2021 10:50 am 
Offline
User avatar

Joined: Sun Mar 28, 2021 7:46 am
Posts: 9
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:
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.

_________________
https://www.github.com/hanzlu/pikobrain


Top
 Profile  
 
 Post subject: Re: Improved RNG for Pikobrain
PostPosted: Tue Sep 14, 2021 7:08 pm 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 3406
Hanzlu wrote:
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.


Top
 Profile  
 
 Post subject: Re: Improved RNG for Pikobrain
PostPosted: Wed Sep 15, 2021 1:38 am 
Offline
User avatar

Joined: Sun Mar 28, 2021 7:46 am
Posts: 9
Octocontrabass wrote:
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:

Image
There the length between patterns is just above 16.

_________________
https://www.github.com/hanzlu/pikobrain


Top
 Profile  
 
 Post subject: Re: Improved RNG for Pikobrain
PostPosted: Wed Sep 15, 2021 6:53 am 
Offline
Member
Member

Joined: Wed Mar 30, 2011 12:31 am
Posts: 504
I use this classic xorshift, which is very robust: https://github.com/klange/toaruos/blob/ ... lib/rand.c

Code:
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.

_________________
toaruos on github | toaruos.org | gitlab | twitter | bim - a text editor


Top
 Profile  
 
 Post subject: Re: Improved RNG for Pikobrain
PostPosted: Wed Sep 15, 2021 11:43 am 
Offline
Member
Member
User avatar

Joined: Mon May 22, 2017 5:56 am
Posts: 586
Location: Flying strange spaceplanes in a distant solar system
Thanks klange, I've ported it to pforth to replace an exceedingly simple 16-bit prng.

_________________
Pixel Forth


Top
 Profile  
 
 Post subject: Re: Improved RNG for Pikobrain
PostPosted: Thu Sep 16, 2021 1:18 pm 
Offline
User avatar

Joined: Sun Mar 28, 2021 7:46 am
Posts: 9
Alright. Now I've been able to utilize the new RNG to make a text based minesweeper game without patterns made by the mines:

Image

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.

_________________
https://www.github.com/hanzlu/pikobrain


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 9 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 6 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group