Random Number Generation

by Created: 05 Jan 2005 Updated: 06 Jun 2014

Do you use rand(), Math.Random(), System.Random, or java.util.Random? These are slow and less random than other algorithms available.

I’m always appalled when a new language comes on the scene (like Java or C#) and it provides nothing better than a linear congruential random number generator. Or when applications that need good random numbers (especially games or simulations) use this same generator. We’ve had better generators for decades. Should we all go back to using punch cards and Fortran, too? We can do better.

Like most software algorithms, random number generation continues to be researched and improved. Thanks to the internet, it doesn’t take much effort to find out about these innovations and stay current with the state-of-the-art. There’s no excuse for using an inferior random number generator.

There are as many different random number generators as there are ways to search a string for a substring. Some that are fast and good include:

These random number generators take up very little space, have very long periods and other useful statistical properties, and are extremely fast – much faster than the standard random number generator that comes with your platform. I used to provide source code here for several of them, but the links above are better resources now. The last one is actually still my implementation. The last three above typically fail the most stringent statistical tests, but are still better than the MLCG generators that used to be standard.

Increasingly, the world is shifting away from CPUs to GPUs for high-performance computation. Philox is currently the fastest on both NVIDIA and AMD GPUs. Parallelized random number generation runs into challenges; for an excellent analysis and solutions, including Philox, see Parallel Random Numbers: As Easy as 1, 2, 3) (Salmon, Moraes, Dror & Shaw, 2011).

Since I first wrote this article in 2005, many new systems have adopted these faster, better RNGs. C++11 now includes the Mersenne Twister, and Python 2 uses it as the standard RNG. However, note that the Mersenne Twister is no longer considered the best possible RNG (speed or statistical properties).

There are many other perhaps less-well-known generators. I’m particularly fond of ISAAC (fast and cryptographically secure) – his other pages about hashing techniques are also worth reading. Warp (GPU-based generator) looks interesting, but I haven’t used it.

Note, it’s not just the random number generator you use, it’s also how you use it. Minor details about how you convert the random number to an interval or an integer can introduce statistical bias or other deficiencies.

Additional Reading