Ian Bullard

Note: This article was originally on my old web site and there was a follow up article that replied to some feedback and cleaned up the source code. I've abandoned that web site and decided to merge the two articles into this one.

Never use rand()!

By the end of this article I will convince you to never use rand() or random() again. Instead you’ll implement your own version or download an existing implementation of a better random number generator.

Why I even thought about implementing rand() myself

I started writing my own game engine sometime in 2002. There had been attempts before then, but this was the first real push to create my own cross-platform 3D game engine from scratch. At the time I was working on fighting games for the Playstation 2 and Xbox with a game engine that was originally written in C for the Playstation.

Being an engineer on a console title is an experience I highly recommend because you end up doing things you normally wouldn’t think of doing for other games. Many established companies have libraries of code that implement what PC and Mac programmers take for granted in the operating system. For instance, when the Xbox first came out I had to write a memory manager for it because there wasn’t one. Other companies I worked for later had entire STL implementations of their own and special implementations of standard C’s math library.

When it came time to write my own game engine, I assumed I should do the same. Seven years later, I don’t recommend independent developers do this because it’s impossible to ship a game that way when you’re working alone. If you’re just programming at home for fun and knowledge I do recommend it, I learned some valuable lessons from that experience. The first thing I learned about is random number generators.

What is rand()?

Standard C’s rand() is an implementation of a pseudorandom number generator (PRNG). In short, a PRNG takes a starting seed number and generates a series of numbers that appear to be random. For rand(), you use srand() to seed the random number generator (usually with a current time value) then use rand() to get the “random” numbers. The C standard doesn’t dictate the algorithm used, it just says that it returns a random number in the range of [0, RAND_MAX].

What alternatives are there?

Before I tell you why rand() shouldn’t be used I’d like to introduce you to a couple of alternatives. PRNGs have different strengths, algorithms used for statistical modeling need PRNGs that are as close to random as possible. Cryptography need to be not only random but also resistant to cryptography attacks. Games need randomness but speed is also important, sometimes more important than how random the algorithm is.

There are many PRNGs available but I’ve settled on three for use in my engine:

• The Mersenne Twister algorithm is used in statistical simulations and is highly recommended. It is the PRNG I’d use when speed isn’t that important.
• ISAAC is a cryptographically strong PRNG. On my Intel Mac Pro it’s just as fast as Mersenne but on other platforms it’s much slower.
• GameRand is a random number generator based off an “Image of the Day” on Flipcode.com (now dead but an archive is available) posted by Stephan Schaem. I changed his assembly language to C++ for my implementation. It’s not a really good PRNG for randomness but it’s incredibly fast.

The tests

Speed

For speed tests I generated 50 million random numbers and reported the number of seconds it took. I ran each speed test five times and took the average. I’ve added BSD’s random() to this test for comparison as well for those folks working on the Mac.

Here’s the results on my Mac Pro with two 2.8 GHz quad-core Intel Xeon processors:

rand() = 5.47 seconds
random() = 3.02 seconds
Mersenne = 4.92 seconds
ISAAC = 4.92 seconds
GameRand = 0.72 seconds

As you can see, rand() is the slowest of the bunch. Mersenne Twister and ISAAC come in a close second and GameRand is by far the fastest. When I first compiled these results I was confused because I thought Mersenne was faster than ISAAC. When I dug up the results on my previous Mac Pro with two 1.8 GHz G5 processors it was more like how I remembered it (I don’t have random() timings for the G5 but I’d expect it to be in between Mersenne and GameRand):

rand() = 9.94 seconds
Mersenne = 7.66 seconds
ISAAC = 13.2 seconds
GameRand = 1.69 seconds

On the G5 ISAAC is 60% slower than Mersenne. This shows you should never make performance assumptions when changing to a new CPU architecture.

Here's the iPod Touch timings, I haven’t ported my crypto code to the iPhone yet so ISAAC isn’t include:

rand() = 19.22 seconds
random() = 7.83 seconds
GameRand = 0.29 seconds
Mersenne = 6.47 seconds

No surprises here, it follows the pattern we saw in the previous tests.

Quality

The quality of a PRNG can be measured by existing tests. I’ve chosen the DieHard random number generator test. For each of the algorithms I listed above I created a file with 5 million values and ran it through the test. Here’s what the test application says about the results:

Most of the tests in DIEHARD return a p-value, which should be uniform on [0,1) if the input file contains truly independent random bits. Those p-values are obtained by p=1-F(X), where F is the assumed distribution of the sample random variable X---often normal. But that assumed F is often just an asymptotic approximation, for which the fit will be worst in the tails. Thus you should not be surprised with occasional p-values near 0 or 1, such .0012 or .9983. When a bit stream really FAILS BIG, you will get p`s of 0 or 1 to six or more places. By all means, do not, as a Statistician might, think that a p < .025 or p> .975 means that the RNG has "failed the test at the .05 level". Such p`s happen among the hundreds that DIEHARD produces, even with good RNGs. So keep in mind that "p happens"

For the sake of this article I’m going to stick to what the author of DieHard suggests, if a p is a 0 or a 1 to six places or more it fails. There are a lot of tests (229) so I’m not going to list the results of every one, instead I’ll give you the percent of tests passed:

rand() = 74% (59 fails)
random() = 72% (64 fails)
Mersenne = 100% (0 fails)
ISAAC = 100% (0 fails)
GameRand = 85% (33 fails)

As you can see, rand() is almost the worst PRNG of the bunch. It’s also the slowest, slower than even ISAAC on Intel Xeon processors. GameRand fails some of the tests but it’s incredibly fast. Depending on your architecture or target use, both Mersenne and ISAAC are quality PRNGs.

Clarifications

1) In most cases the speed of your PRNG is a non-issue. The randomness of it is an issue especially in games. Players can notice the difference between rand() and Mersenne Twister in games where you show them the number results (like in role-playing games).

2) If speed does become an issue it’s nice to be able to fall back on a known solution. For instance generating terrain requires a lot of random numbers.

3) Yeah, in the end my time spent researching PRNGs was probably not well spent. It was my time though, and I’m O.K. with that.

Most of the criticisms of this original article came from the performance aspects but ignored that both rand() and random() have results that fail DieHard tests. C++0x is replacing rand() with multiple generator types, including Mersenne Twister. Why? Because rand() isn’t random.

Summary

Don’t use rand() or random(), they’re slow and not that random. As you’ll see below, GameRand is so simple you can memorize it and is significantly faster and more random than both rand() and random(). If you need a really good PRNG, use Mersenne Twister.

Just say no to rand()!


Source Code for GameRand

I've uploaded three implementations of GameRand:

C: gamerand.c

C++: GameRand.hpp

Robert Græsdal sent me a JavaScript version: gamerand.js