What type of random number engine to use with a specified random distribution?

Question

The C++11 way of generating random numbers is:

Instantiate a random number engine
Instantiate a random distribution
Push the random numbers from the engine through the distribution

The problem is that both a random number engine and a random distribution are templated with respect to the type of arithmetic you are using.

How do these two types of arithmetic need to be related?

Can you use a 32 bit integer for the engine and a 64 bit integer for the distribution and opposite? What are the dangers? What about floating point types?

I hypothesize a guideline that the number of possible numbers generated by an engine should be greater or equal than the number of distinct random numbers you are hoping to get. Unfortunately I was not able to test my hypothesis, since on my computer uint_fast32_t and uint_fast64_t are the same and therefore both suggested engines for each of the three C++11 generators produce the same results.

The documentation on C++11 distributions like std::uniform_real_distribution or std::uniform_int_distribution is incomplete in this regard:

This section is incomplete. Reason: requirements on Generator

But for exapmple the gcc 4.7 implementation of uniform_real_distribution is:

  template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng,
       const param_type& __p)
{
  __detail::_Adaptor<_UniformRandomNumberGenerator, result_type>
    __aurng(__urng);
  return (__aurng() * (__p.b() - __p.a())) + __p.a();
}

Where the Adaptor is:

An adaptor class for converting the output of any Generator into the input for a specific Distribution.

The "any" sounds reassuring, but is it standard? I am especially worried about hidden overflows that are hard to detect and which may compromise the correctness of the distribution.

The requirements can be found in open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf (pages 904 onwards). I could not find an answer, but maybe you can? — Escualo

rici rici · Accepted Answer · 2013-07-26T03:24:56

You're allowed to use any uniform random number generator (URNG) for any distribution function. The distribution function is assumed to know what it needs, and the URNG is required to describe what it provides, so that the distribution function can request sufficient entropy for its needs. (Note that an "engine" is a URNG, with some additional requirements like seedability.)

The "universal" adaptor you mention from the GNU standard library implementation takes a uniform random number generator G (actually it's name is much longer, but that will get tedious) and a result type R, which must be a numeric type. G must define G::min and G::max, the minimum and maximum values it can return, and it is supposed to return all values between those limits with equal probability. So it's easy to know how many bits of randomness are available from a call to G(). Moreover, from numeric_limits<R> will tell us how many bits are needed for an R. So dividing the entropy required by the entropy available tells the adaptor how many times it needs to call G to produce a uniformly random R. So the adaptor takes any URNG/engine which produces some result type, and adapts it to produce a different result type.

What type of random number engine to use with a specified random distribution?

1 Answers