Xorshift RNGs for small systems

"Xorshift RNGs" by George Marsaglia describes a very efficient system for generating high-quality random numbers using very little compute and storage.

For a simple random number generator running on an embedded CPU we're unlikely to be very concerned with cycle lengths -- a cycle of 2³²-1 is perfectly acceptable. Marsaglia suggests coefficients (13, 17, 5) for a 32-bit generator. So we have C code:

uint32_t seed = 7;  // 100% random seed value

static uint32_t random()
{
  seed ^= seed << 13;
  seed ^= seed >> 17;
  seed ^= seed << 5;
  return seed;
}

This is simple enough to give excellent performance on an 8-bit CPU. Note that seed never reaches zero; in fact if seed is zero then random() returns zero every time.

This 32-bit ANS Forth implementation also has a setseed function which can be safely called with any 32-bit integer. setseed handles the problem value of 0 by mapping it to -1.

variable seed
7 seed !

: random    ( -- x )  \ return a 32-bit random number x
    seed @
    dup 13 lshift xor
    dup 17 rshift xor
    dup 5  lshift xor
    dup seed !
;

: setseed   ( x -- )  \ seed the RNG with x
    dup 0= or         \ map 0 to -1
    seed !
;

As a quick trial, plotting 65536 random pixels in a 256x256 grid on a Gameduino 2 gives no obvious patterns: