Random Engine Differences

Question

The C++11 standard specifies a number of different engines for random number generation: linear_congruential_engine, mersenne_twister_engine, subtract_with_carry_engine and so on. Obviously, this is a large change from the old usage of std::rand.

Obviously, one of the major benefits of (at least some) of these engines is the massively increased period length (it's built into the name for std::mt19937).

However, the differences between the engines is less clear. What are the strengths and weaknesses of the different engines? When should one be used over the other? Is there a sensible default that should generally be preferred?

Answer 1

From the explanations below, linear engine seems to be faster but less random while Marsenne Twister has a higher complexity and randomness. Subtract-with-carry random number engine is an improvement to the linear engine and it is definitelly more random. In the last reference, it is stated that Mersenne Twister has higher complexity than the Subtract-with-carry random number engine

Linear congruential random number engine

A pseudo-random number generator engine that produces unsigned integer numbers.

This is the simplest generator engine in the standard library. Its state is a single integer value, with the following transition algorithm:

x = (ax+c) mod m

Where x is the current state value, a and c are their respective template parameters, and m is its respective template parameter if this is greater than 0, or numerics_limits::max() plus 1, otherwise.

Its generation algorithm is a direct copy of the state value.

This makes it an extremely efficient generator in terms of processing and memory consumption, but producing numbers with varying degrees of serial correlation, depending on the specific parameters used.

The random numbers generated by linear_congruential_engine have a period of m. http://www.cplusplus.com/reference/random/linear_congruential_engine/

Mersenne twister random number engine

A pseudo-random number generator engine that produces unsigned integer numbers in the closed interval [0,2^w-1].

The algorithm used by this engine is optimized to compute large series of numbers (such as in Monte Carlo experiments) with an almost uniform distribution in the range.

The engine has an internal state sequence of n integer elements, which is filled with a pseudo-random series generated on construction or by calling member function seed.

The internal state sequence becomes the source for n elements: When the state is advanced (for example, in order to produce a new random number), the engine alters the state sequence by twisting the current value using xor mask a on a mix of bits determined by parameter r that come from that value and from a value m elements away (see operator() for details).

The random numbers produced are tempered versions of these twisted values. The tempering is a sequence of shift and xor operations defined by parameters u, d, s, b, t, c and l applied on the selected state value (see operator()).

The random numbers generated by mersenne_twister_engine have a period equivalent to the mersenne number 2^((n-1)*w)-1.http://www.cplusplus.com/reference/random/mersenne_twister_engine/

Subtract-with-carry random number engine

A pseudo-random number generator engine that produces unsigned integer numbers.

The algorithm used by this engine is a lagged fibonacci generator, with a state sequence of r integer elements, plus one carry value. http://www.cplusplus.com/reference/random/subtract_with_carry_engine/

Lagged Fibonacci generators have a maximum period of (2k - 1)*^(2M-1) if addition or subtraction is used. The initialization of LFGs is a very complex problem. The output of LFGs is very sensitive to initial conditions, and statistical defects may appear initially but also periodically in the output sequence unless extreme care is taken. Another potential problem with LFGs is that the mathematical theory behind them is incomplete, making it necessary to rely on statistical tests rather than theoretical performance. http://en.wikipedia.org/wiki/Lagged_Fibonacci_generator

And finally: The choice of which engine to use involves a number of tradeoffs: the linear congruential engine is moderately fast and has a very small storage requirement for state. The lagged Fibonacci generators are very fast even on processors without advanced arithmetic instruction sets, at the expense of greater state storage and sometimes less desirable spectral characteristics. The Mersenne twister is slower and has greater state storage requirements but with the right parameters has the longest non-repeating sequence with the most desirable spectral characteristics (for a given definition of desirable). in http://en.cppreference.com/w/cpp/numeric/random

Answer 2

I think that the point is that random generators have different properties, which can make them more suitable or not for a given problem.

• The period length is one of the properties.
• The quality of the random numbers can also be important.
• The performance of the generator can also be an issue.

Depending on your need, you might take one generator or another one. E.g., if you need fast random numbers but do not really care for the quality, an LCG might be a good option. If you want better quality random numbers, the Mersenne Twister is probably a better option.

To help you making your choice, there are some standard tests and results (I definitely like the table p.29 of this paper).

---

EDIT: From the paper,

1. The LCG (LCG(***) in the paper) family are the fastest generators, but with the poorest quality.
2. The Mersenne Twister (MT19937) is a little bit slower, but yields better random numbers.
3. The substract with carry ( SWB(***), I think) are way slower, but can yield better random properties when well tuned.