CODEWITHSUNDEEP
c++mathrandommersenne-twister
Rob Spencer
Rob Spencer

Reputation: 51

Mathematics behind default_random_engine and normal_distribution in C++

Can anyone lead me to somewhere that actually talks about the mathematics that underpin these two normal_distribution and default_random_engine. From what i understand uses a Mersenne twister? If so can anyone point me in the direction of some online resource that explains how this pseudo random algorithm actually works if that is what it uses, because i cant find much on the mersenne twister. Also if the number is uniform, which most pseudo random algorithms outputs are, then how does normal_distribution make it normally distributed? Does it use inverse transform, box muller or ziggurat perhaps? Any help i would really appreciate :)

Upvotes: 2

Views: 294

Answers (1)

andand
andand

Reputation: 17487

There are a few issues you're asking about. The first regards methods to generate a sequence of pseudo random numbers, usually integers. Wikipedia has a reasonable description of the Mersenne Twister (MT) as well as the Linear Congruential Generator (LCG) both of which perform that function. These are intended to more or less uniformly distribute integers throughout the effective range and represent the core functionality required to generate more complicated distributions.

Generating numbers from other distributions can be performed by pulling numbers from one of the methods which generated uniformly distributed integer pseudo-random draws. There are a number of methods for doing this:

  1. Inverse Transform Sampling - If the inverse of the CDF of the distribution has a closed form, a draw from U(0,1) can be used to generate draws from the underlying PDF.
  2. Identities - Some distributions can be generated through the use of identities of other distributions. The normal distribution falls into this category, since there is no closed form of its inverse CDF. There are several methods which can be used to generate draws from a standard normal distributions.
  3. User Defined Distribution - If there is no closed form, or there are not suitable identities available to generate variates, a developer can approximate a PDF by taking samples and creating a histogram of the PDF. This can then be used to build an approximation of the CDF and its inverse, from which draws can be made.
  4. Rejection Sampling - This method generates variates from a PDF by rejecting draws from a different PDF which do not adhere to the properties of the desired PDF.

If you are looking for specific implementation details for the C++ class libraries for the Mersenne Twister, you could look at the Boost source code which will provide some insight into how Boost does it. AFAIK, C++11 standard doesn't specify how this is to be implemented, only how it should behave. Implementation is left to the compiler developers, but I would be surprised if many of the more common compilers use something other than the Boost implementation (Update: though MSalters' observation below is one reason why a particular compiler would do something else). The same holds for the Boost normal_distribution class.

Upvotes: 5

Related Questions