RNG - or how to create randomness from a deterministic computer

Hello world,

Today, I worked on implementing a xorshift RNG algorithm for the gameboy. It’s based on this implementation in C.

Pseudo code corresponding to the assembly version I implemented looks like this :

void rng() {
    t = x ^ (x << 4);
    h = t ^ (t << 1);
    x = y;
    y = z;
    z = a;
    a = z ^ (z >> 1);
    a = a ^ h
    return a
}

A xorshift algorithm is quite easy to implement, fast (20 instructions), and remarkably good at producing randomness.

The one big flaw I can see is that it stores its state in 4 bytes of memory, which slows it down a little, however, it does help increase the cycle length, which is quite good for such a small algorithm. With an initial state of (0,0,0,1) it would take 2 years to go back where we started, if we generated a number each frame.

Our next goal for this RNG is to find a source of entropy to initialize it, we are leaning towards reading the initial state of the WRAM, but discussions are still taking place.

See ya !

Dorian