Random Number Generation: The what, why and how

Many computer scientists are absolutely crazy about random numbers. On first thought it sounds a little bit odd, but upon further inspection it's easy to see why. You can use them for generating random loot in a game, or making a monster walk around randomly. Or in cryptography. The possibilities are endless! In addition, sometimes it is desirable to repeat a particular sequence of numbers without storing them all, and sometimes the opposite is true. In this post I intend to explain what a pseudo-random number generator is, why you'd want one, and where you can get your own.

Unfortunately, although computers are really good at complicated calculations, they are totally rubbish at generating true random numbers (that's what random.org is for). All is not lost though - we can still generate long sequences of numbers using a pseudo-random number generator (PRNG).

There are many different algorithms in several different families, but they all rely on a few basic principles. All PRNGs start with a seed, do something to transform the seed, and produce an output. Some algorithms store a few of the previously generated numbers to feed them back into the algorithm too. All PRNGs also have a period, which is the number of random values they can produce before they start to repeat themselves. Usually this value is so high that it doesn't mattter.

The seed, in this case, is a value that is used to initialise the random number generator and give it something to work with. Because PRNGs aren't truly random, any given seed will always produce the same sequence of random numbers. This can be useful if you want to allow players of your game to share cool maps that they've found without having to store details of every single item.

PRNGs can also be measured in terms of the 'quality' of the random numbers they produce. This sounds like a difficult thing to measure, and it is. The easiest (but probably not the best - I don't know, I'm not an expert!) way to test the quality of a random number generator is to generate a whole bunch of random bytes, save them to a file, and try to compress it. A true sequence of random numbers should be uncompressible. Besides, nobody wants a poor-quality random number generator.

After all that, we can finally get around to the algorithms themselves. there are 3 categories that I know of:

Linear Congruential Generators (LCGs)

Your bog standard (poor quality) generator. Usually has relatively short period too. The only good thing about these is their speed.

Mersenne Twister

Slower, but have an insanely large period (2²¹⁹⁹³⁷ − 1 to be exact). Output is of a high quality.

XOR bitshifters

A family of fast, high-quality generators. Variable period, depending on the algorithm you pick. Also very easy to implement. See below for more information.

There may be others, but these are the 3 that I've seen around (suggestions of algorithm families are welcome in the comments).

Since XOR bit shifters are the new up-and-coming thing, I'll elaborate on them a little bit. There are actually a bunch of different algorithms in this family:

• xorshift
• xorshift1024*
• xorshift128+
• xoroshiro128+
• ....

Their history is a bit complicated, so I won't go into any detail, but basically it all started with the xorshift algorithm. The xorshift* family followed as an improvement afterwards, and the xorshift+ family is the result of another (but different) improvement made by tweaking the original algorithm slightly. Finally, the xoroshiro+ set are new and include yet another improvement based on xorshiro+. This article sums them up nicely, along with a suggestion as to when you should use each.

The number in the names of the above refer to the number of bits that each uses to store its state. Apparently each algorithm is available in 64, 128, 256, 1024, and probably even more flavours, but the above are the most popular.

Implementations

To end this post, I'm going to include some links to implementations of the algorithms mentioned in this post in various languages. This (certainly) isn't an exhaustive list, but should serve as a good starting point if you are on the hunt for a random number generator for your next project.

• xorshift128+ - Javascript, C#, C++
• xorshift - C#, C, C++
• xorshift1024* - C++, C
• multiply-with-carry¹ - C#
• Mersenne Twister - Javascript, C# 1, C# 2, C++

Sources

• A comparison between different XOR bitshifting algorithms
• XORshifters on Wikipedia
• List of pseudo-random number generators

1. The multiply-with-carry (aka MWC) algorithm apparently come under xor bitshifters, but I' haven't mentioned it to as to keep things (relatively) simple. More information can be found here.

Update 5th Jan 2017: Fixed a typo.