uniform_int_distribution with zero range goes to infinite loop

user_1151582 0
Viewed 250

For unit tests I implemented a mock random number generator. I believe that this is a valid implementation of UniformBitGenerator (the mock actually uses google mock to set the return of operator(), but it behaves the same).

struct RNG
{
    using result_type = size_t;
    static result_type min() { return 0; }
    static result_type max() { return std::numeric_limits<result_type>::max(); }
    result_type operator()() { return max(); }
};

Now I use this mock to sample from std::uniform_int_distribution in the range [a, b], a == b. I believe this is allowed, the only restriction I have found here on the parameters of the distribution is b >= a. So I would expect the following program to print 5.

int main()
{
    auto rng = RNG();
    auto dist = std::uniform_int_distribution<>(5, 5);
    printf("%d\n", dist(rng));
    return 0;
}

Instead it goes into an infinite loop inside the STL, repeatedly drawing numbers from the generator but failing to find a number within the specified range. I tested different (current) compilers (including clang, gcc, icc) in different versions. RNG::max can return other values (e.g. 42) as well, doesn't change anything.

The real code I'm testing draws a random index into a container which may contain only one element. It would be easy to check this condition but it's a rare case and I would like to avoid it.

Am I missing something in the specification of RNGs in the STL? I'd be surprised to find a bug in ALL compilers ...

language-lawyer std random c++
2 Answers

A uniform distribution is usually achieved with rejection sampling. You keep requesting random numbers until you get one that meets the criteria. You've set up a situation where the criteria can't be met, because your random number generator is very non-random, so it results in an infinite loop.

Mark_Ransom_59870

The standard says ([rand.dist.uni.int]):

A uniform_­int_­distribution random number distribution produces random integers i, a ≤ i ≤ b, distributed according to the constant discrete probability function

  P(i|a,b)=1/(b−a+1)

. . .

explicit uniform_int_distribution(IntType a = 0, IntType b = numeric_limits<IntType>::max());

  Requires: a ≤ b.

So uniform_int_distribution<>(5,5) should return 5 with probability 1/1.

Implementations that go into an infinite loop instead, have a bug.

However, your mock RNG that always generates the same value, doesn't satisfy Uniform random bit generator requirements:

A uniform random bit generator g of type G is a function object returning unsigned integer values such that each value in the range of possible results has (ideally) equal probability of being returned. [ Note: The degree to which g's results approximate the ideal is often determined statistically.  — end note ]

See [req.genl]/p1.b:

Throughout this subclause [rand], the effect of instantiating a template:

b) that has a template type parameter named URBG is undefined unless the corresponding template argument is cv-unqualified and satisfies the requirements of uniform random bit generator.

Sure enough, with a standard RNG it just works:

#include <iostream>
#include <random>

int main() {
    std::mt19937_64 rng;
    std::uniform_int_distribution<> dist(5, 5);
    std::cout << dist(rng) << "\n";
}

Prints:

5
user_4853430
Related