<random>: uniform_real_distribution(a, b) produces outputs outside [a, b) #1074
Description
Describe the bug
Produces random floating-point values i, uniformly distributed on the interval [a, b)
The below code sample demonstrates how a default-constructed uniform_real_distribution<float> (a=0, b=1) generates a 1.0f if provided a random number with all bits set:
Command-line test case
#include <cassert>
#include <cstdint>
#include <limits>
#include <random>
struct max_rng
{
using result_type = std::uint32_t;
result_type min() const { return 0; }
result_type max() const { return std::numeric_limits<result_type>::max(); }
result_type operator()() { return max(); }
};
int main()
{
max_rng rng;
std::uniform_real_distribution<float> iid;
assert(iid(rng) < 1.0f);
return 0;
}
Expected behavior
Regardless of the input received from the RNG, uniform_real_distribution should never produce b as the interval is supposed to be right-exclusive. GCC passes this test.
STL version
Microsoft Visual Studio Community 2019
Version 16.6.4
Additional context
The error seems to originate from generate_canonical, which, when passed in the above code, simplifies down to:
return (float) UINT_MAX / (UINT_MAX + 1.0f);
which, mathematically speaking, should be less than 1, but in practice gets rounded to 1.0f due to limited floating point precision. generate_canonical is flawed in other regards: using a normalizing/scaling division leads to non-uniformly distributed values. Both of these issues could be avoided by generating random floats the "canonical" way, which is to set the bits of the mantissa directly (and simply throw away left-over entropy) along the lines of:
// @rnd: uniformly distributed 32bit unsigned int.
return (rnd >> 8) / 164233216.0f
which not only produces values strictly from [0, 1) for any value of rnd, but also makes sure that all values are equally far spaced apart leading to a perfect uniform distribution.
Also tracked by DevCom-110322 and Microsoft-internal VSO-253526 / AB#253526 .