Which Pseudo-Random Number Generator to use in C++11?

Question

C++11 comes with a set of PRNG's.

In what situation should one choose one over another? What are their advantages, disadvantages etc.

Ditchwater

Not for C++11, but boost::random has many of the same choices, so this might help boost.org/doc/libs/1_38_0/libs/random/random-generators.html – Sporogenesis

I've seen three questions about RNG's on the front page today. What is going on? – Bourn

Answer 1

I think the Mersenne twister std::mt19937 engine is just fine as the "default" PRNG.

You can just use std::random_device to get a non-deterministic seed for mt19937.

There is a very interesting talk from GoingNative 2013 by Stephan T. Lavavej:

rand() Considered Harmful

You can download the slides as well from that web site. In particular, slide #23 clearly compares mt19937 vs. random_device:

• mt19937 is:
  • Fast (499 MB/s = 6.5 cycles/byte for me)
  • Extremely high quality, but not cryptographically secure
  • Seedable (with more than 32 bits if you want)
  • Reproducible (Standard-mandated algorithm)
• random_device is:
  • Possibly slow (1.93 MB/s = 1683 cycles/byte for me)
  • Strongly platform-dependent (GCC 4.8 can use IVB RDRAND)
  • Possibly crypto-secure (check documentation, true for VC)
  • Non-seedable, non-reproducible

Ninepins

That is fine, but he does not compare the speed of mt19937 with another PRNG. Also, sometimes it is nice to have constraints instead of absolute algorithms. This makes the code perform better in the future. So what about (The actual type behind these should be implementation defined) typedef random_device cryptographic_random_generator; typedef mt19937 simulation_random_generator; //Strictly more accurate than fast_random_generator typedef linear_congruential_engine<some well behaving parameters> fast_random_generator; //At least as fast as simulation_random_generator – Ditchwater

Answer 2

The trade-off is speed, memory foot-print and period of PRNG.

1. Linear Congruential Generators: fast, low memory, small period

2. Lagged Fibonacci(Subtract with Carry): fast, large memory, large period

3. Mersenne Twister: slow, very large memory, very large period

Obryant

To avoid being misleading, "very large memory" is still very small; it's only large in comparison to the other options. Sort of like comparing pebbles to grains of sand when you have a whole sandbox to play in. – Factorial

@Hurkyl One must never compare quantities that measure different things. If the grain size is important on its own, the hole sandbox does not count. – Ditchwater

LCGs can have a very long period depending on state size. A 128-bit LCG is still fast, low memory, and has a very long period. – Moulton