Random: Xorshift

July 2003 George Marsaglia introduced the world to xorshift random number generators.  His claim that they “pass tests of randomness very well” is arguable.  His claim that they are “simple, extremely fast random number generators” is not.  They are definitely simple and extremely fast.  They also produce small code.  A perfect candidate for the Tiny Core!

All combinations of 32-bit triples and xorshift formulas were tested using dieharder.  Marsaglia’s “favorite” seems to perform better than the others.  However, it also produces slightly larger and slightly slower code.

Size

Marsaglia’s favorite adds 126 bytes to the image which is significantly less than the 454 bytes added by the Libc random function.

Speed

On a 1 MHz ATtiny85 processor Marsaglia’s favorite takes 0.323 milliseconds to generate the next value which is significantly faster than the 1.947 milliseconds taken by the Libc random function.

Quality

On the dieharder tests, Marsaglia’s favorite (and the other xorshift generators) always fails four tests including: diehard_rank_32x32, diehard_count_1s_str, rgb_bitdist, dab_monobit2.

Seeds

Valid seeds are in the range 1 to 232-1 (0xFFFFFFFF).  Zero is the only bad seed and is fatal.

References

Leave a Reply