Better C++ Pseudo Random Number Generator
Yesterday I wrote about the terrible quality of the default pseudo random number generators in the C++ standard library. The article came to the conclusion they’re all around terrible, and should generally be avoided, yet, it didn’t provide any alternatives. Therefore, today I’ll provide you with three very good alternatives to the existing generators in the C++ standard library.
They’re almost fully compliant to the standard, and should be an almost drop-in replacement for the old generators.
There is a minor change in the interface, related how the generator is seeded. To seed any of the generators, you need to pass in the std::random_device (or any class which implements operator() and returns an unsigned int) you want to use, instead of just the seed. By doing so, I can make sure each generator is seeded accordingly.
Each of these is passing both the PractRand and BigCrush test. The raw PractRand test results can be found here and the code can be found at the end of the article.
Comparison
For comparison, I’ve reproduced the comparison tables from the previous article. The newly added generators are highlighted in bold.
| generator | 512M | 1G | 2G | 4G | 8G | 16G | 32G | 64G | 128G | 256G | 512G | 1T | 2T |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ranlux24_base | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ |
| ranlux48_base | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ |
| minstd_rand | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ |
| minstd_rand0 | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ |
| knuth_b | ✓ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ |
| mt19937 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✗ | ✗ | ✗ | ✗ |
| mt19937_64 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✗ | ✗ | ✗ |
| ranlux24 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| ranlux48 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| splitmix | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| xorshift | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| pcg | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
All three generators have excellent statistical quality, while having a smaller footprint and being faster. As a bonus, each of the three generators can be implemented in less than 10 lines of code, making them super easy to port to other environments or languages.
| Name | Predictability | Performance | State | Period |
|---|---|---|---|---|
| Mersenne Twister | Trivial | Ok | 2 KiB | 2^19937 |
| LCG (minstd) | Trivial | Ok | 4-8 byte | <= 2^32 |
| LFG (ranluxXX_base) | Trivial | Slow | 8-16 byte | <= 2^32 |
| Knuth | Trivial | Ok | 1KiB | <= 2^32 |
| ranlux | Unknown? | Super Slow | ~120 byte | 10^171 |
| splitmix | Trivial | Fast | 8 byte | 2^64 |
| xorshift | Yes | Fast | 8 byte | 2^64 |
| pcg | Unknown | Fast | 16 byte | 2^128 |
Example
Following is an example of how to generate 10 random die rolls using the supplied pcg generator:
#include <stdio.h>
#include "random.h"
int main()
{
std::random_device rd;
pcg rand(rd);
std::uniform_int_distribution<> u(1, 6);
for (int i = 0; i < 10; ++i)
printf("%d\n", u(rand));
}
Code
Code can be found in the following gist.
truncated xorshift32*