C++ uniform_int_distribution always returning min() on first invocation

by

Explanation for the observed behavior

This is how uniform_int_distribution maps the random bits to numbers if the range of possible outcomes is smaller than the range of number the rng produces:

const __uctype __uerange = __urange + 1; // __urange can be zero
const __uctype __scaling = __urngrange / __uerange;
const __uctype __past = __uerange * __scaling;
do
  __ret = __uctype(__urng()) - __urngmin;
while (__ret >= __past);
__ret /= __scaling;

where __urange is larger - smaller and __urngrange is the difference between the maximum and the minimum value the rng can return. (Code from bits/uniform_int_dist.h in libstdc++ 6.1)

In our case, the rng default_random_engine is a minstd_rand0, which yields __scaling == 195225785 for the range [0,10] you tested with. Thus, if rng() < 195225785, the distribution will return 0.

The first number a minstd_rand0 returns is

(16807 * seed) % 2147483647

(where seed == 0 gets adjusted to 1 btw). We can thus see that the first value produced by a minstd_rand0 seeded with a number smaller than 11615 will yield 0 with the uniform_int_distribution< int > distribution( 0, 10 ); you used. (mod off-by-one-errors on my part. 😉 )

You mentioned the problem going away for bigger seeds: As soon as the seeds get big enough to actually make the mod operation do something, we cannot simply assign a whole range of values to the same output by division, so the results will look better.

Does that mean (libstdc++’s impl of) <random> is broken?

No. You introduced significant bias in what is supposed to be a random 32 bit seed by always choosing it small. That bias showing up in the results is not surprising or evil. For random seeds, even your minstd_rand0 will yield a fairly uniformly random first value. (Though the sequence of numbers after that will not be of great statistical quality.)

What can we do about this?

Case 1: You want random number of high statistical quality.

For that, you use a better rng like mt19937 and seed its entire state space. For the Mersenne Twister, that’s 624 32-bit integers. (For reference, here is my attempt to do this properly with some helpful suggestions in the answer.)

Case 2: You really want to use those small seeds only.

We can still get decent results out of this. The problem is that pseudo random number generators commonly depend “somewhat continuously” on their seed. To ship around this, we discard enough numbers to let the initially similar sequences of output diverge. So if your seed must be small, you can initialize your rng like this:

std::mt19937 rng(smallSeed);
rng.discard(700000);

It is vital that you use a good rng like the Mersenne Twister for this. I do not know of any method to get even decent values out of a poorly seeded minstd_rand0, for example see this train-wreck. Even if seeded properly, the statistical properties of a mt19937 are superior by far.

Concerns about the large state space or slow generation you sometimes hear about are usually of no concern outside the embedded world. According to boost and cacert.at, the MT is even way faster than minstd_rand0.

You still need to do the discard trick though, even if your results look good to the naked eye without. It takes less than a millisecond on my system, and you don’t seed rngs very often, so there is no reason not to.

Note that I am not able to give you a sharp estimate for the number of discards we need, I took that value from this answer, it links this paper for a rational. I don’t have the time to work through that right now.

More Related Contents:

  1. Structure size so big, need optimization
  2. Decrementing a pointer with an unsigned “negative” number
  3. Random generation of numbers? [closed]
  4. What is the difference between g++ and gcc?
  5. Why is the use of rand() considered bad?
  6. Unmangling the result of std::type_info::name
  7. Compiling a C++ program with GCC
  8. explicit specialization of template class member function
  9. Does MinGW-w64 support std::thread out of the box when using the Win32 threading model?
  10. GCC style weak linking in Visual Studio?
  11. How to create a static library with g++?
  12. GCC C++ “Hello World” program -> .exe is 500kb big when compiled on Windows. How can I reduce its size?
  13. Linking libstdc++ statically: any gotchas?
  14. Error enabling openmp – “ld: library not found for -lgomp” and Clang errors
  15. Is this C++11 regex error me or the compiler?
  16. C++ new operator thread safety in linux and gcc 4
  17. rand() generating the same number – even with srand(time(NULL)) in my main!
  18. Link errors using members in C++17
  19. Generating m distinct random numbers in the range [0..n-1]
  20. How to use OpenSSL with GCC?
  21. How to define a string literal in gcc command line?
  22. Is there a compiler bug exposed by my implementation of an is_complete type trait?
  23. Undefined reference to google::protobuf::internal::empty_string_[abi:cxx11]
  24. Why do the usual access control checking applies to names used to specify explicit instantiation when accessed through template parameters?
  25. Can nullptr be emulated in gcc?
  26. How do I temporarily disable a macro expansion in C/C++?
  27. Does GCC inline C++ functions without the ‘inline’ keyword?
  28. Measuring exception handling overhead in C++
  29. How to make sure that std::random_shuffle always produces a different result?
  30. Undocumented GCC Extension: VLA in struct

Leave a Comment