In C, since time immemorial, the easiest way of getting a random number is thus:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    srand(time(NULL));
    int nRandom = rand();
    printf("%d\n", nRandom);
    return 0;
}

Of course, this only gets you part of the way there. The problems with rand() are well-known and well-documented, but the brief summary is:

  • rand() only provides you with a random number up to RAND_MAX, which, on many compilers (including Visual Studio), is 0x7FFF.
  • rand() uses a static context. That is, I cannot have two separate Random Number Generators (RNGs) running at the same time with different seeds.
  • Less interestingly for us, but still nonetheless true, rand() is not acceptable for use in cryptography situations

I could go on and on, but this post isn’t about what’s wrong with rand(). rand() is just a starting point. What we’re after is an RNG that is effective and efficient for use in games. Specifically, we need it to have the following properties:

  • It must be small (memory-wise)
  • It must be fast
  • It must be deterministic given the same seed
  • It must have a long enough cycle that any practical day-to-day use will not experience the cycles
  • It must have a non-static context

Please note:

  • If you need an RNG for cryptographic purposes, use a library that is cryptographically strong. I repeat, none of this subject matter applies to any security or cryptographic subject!

The quote-unquote “standard” wisdom prevalent on the Internet is “Just use Mersenne Twister and be done with it.” Hmmm… What is this “Mersenne Twister”? Wikipedia to the rescue! Wikipedia also has a link to the Mersenne Twister home page. So, let’s examine Mersenne Twister against the above requirements: it’s deterministic, long-cycled, and has a non-static context. All good things. The algorithm is simple and seems fast. However, we’re not going to delve into the speed issue, because my eye is immediately drawn to the following line at the very beginning of the pseudocode presented in the Wikipedia page:

// Create a length 624 array to store the state of the generator
int[0..623] MT
int index = 0

In other words, the Mersenne Twister context uses up 2500 bytes! That’s 2.5K for an RNG! Granted, a very good one, but still…2.5K! Surely we can do better than that.

Next time: how we can do better.