uniform_int_distribution with zero range goes to infinite loop

Question

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 ...

[What's the difference between “STL” and “C++ Standard Library”?](https://stackoverflow.com/questions/5205491/whats-the-difference-between-stl-and-c-standard-library) — François Andrieux, Aug 25 '20 at 16:04
Nice. For `std::uniform_int_distribution<>(a, b);` the behaviour is undefined if `a > b`, but I'm not sure about `a == b`. — Bathsheba, Aug 25 '20 at 16:04
The min/max functions of RNG are not constexpr which is required by the BitGenerator concept. — ALX23z, Aug 25 '20 at 16:29
it does work with an actual random number generator as that doesn't return it's max value repeatedly. — DanielAbele, Aug 25 '20 at 16:29
As @ALX23z points out, this `static_assert(std::uniform_random_bit_generator);` check fails. Adding `constexpr` passes the check, and still times out. — cigien, Aug 25 '20 at 16:31
My guess is this is a bug. And returning 42 does [work](https://godbolt.org/z/vbdsr6) — cigien, Aug 25 '20 at 16:33

score 4 · Answer 1 · answered Aug 25 '20 at 16:43

4

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.

answered Aug 25 '20 at 16:43

Mark Ransom

299,747
42
398
622

Yes, it seems that the max value is rejected https://godbolt.org/z/M8KPTY (and the optimizer catches this case https://godbolt.org/z/6qYe56) – Bob__ Aug 25 '20 at 16:46

rustyx · Accepted Answer · 2020-08-25T16:35:21.963

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:

At least looking at the implemenation with libstdc++ that comes with gcc7.5, the problem is with how it's scaling the rng range vs. the requested range. In this particular case, any value other than max() will exit the loop (since the requested range length is zero). Definitely a bug, or at least an edge case that isn't handled well. If the OP 'RNG' returned 0, it wouldn't hit the problem. — Dave S, Aug 25 '20 at 16:34
I didn't think about the requirement that the generator is actually random. This would also explain the complexity requirement of uniform_int_distribution: `Amortized constant number of invocations of g.operator()`. It's unfortunate, because by mocking I was exactly trying to get rid of randomness. That would mean it's only possible (within the standard) to mock the distribution, not the actual generator. Which is more work if you are using different distributions. — DanielAbele, Aug 25 '20 at 16:41

uniform_int_distribution with zero range goes to infinite loop

2 Answers2