Front Page Archive

Cessen's Ramblings

2012 - 06 - 26

Pseudo-Random Number Generators

Holy crap it's been a long time since I've blogged here. And you know what? I'm fine with that. I'll blog when I actually have something I want to share. Like now, for example.

So, I've been pecking away at a 3d renderer that I've dubbed "Psychopath". I've put it up on GitHub: https://github.com/cessen/psychopath_cpp

Anyway, I'm discovering all sorts of nifty little things as I'm working on this, many of which are handy and general-purpose. The latest one is a simple pseudo-random number generator that is quite robust.

For most simulation applications (advanced 3d rendering can be considered such) the included random functions in e.g. most C or C++ standard libraries are insufficient. Moreover, it is important to be able to guarantee that the RNG you are using is consistent across platforms and satisfies specific properties of randomness. Therefore it is generally a good idea, in these applications, to include a custom RNG implementation and use that.

The go-to RNG for such purposes these days is the Mersenne Twister, and as such that is the RNG I've been using in Psychopath up to this point. But the code for it is quite complex. And as it turns out, there are other RNG's out there that are pretty much just as good, but have far simpler code.

Several such RNG's are covered in the short and accessible paper "Good Practice in (Pseudo) Random Number Generation for Bioinformatics Applications" by David Jones. I have opted to use his JKISS generator, which is a variation on George Marsaglia's KISS (Keep It Simple Stupid) RNG.

You can see my implementation here.

The generator has very good statistical properties, passing a large battery of intensive tests as outlined in the paper. In fact, it appears to be just as robust as the Mersenne Twister in almost every respect. The only way in which is it less robust is period length. Mersenne Twister has the enormous period 2^19937-1, whereas JKISS has a period of roughly 2^127. JKISS's period is still very large, however, and is very appropriate for most practical applications, 3d rendering included.

For applications that require larger periods, several other simple-yet-robust generators are also listed in the paper, some of which have enormous periods exceeding even the Mersenne Twister.