René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"\u003crandom\u003e: uniform_real_distribution(a, b) produces outputs outside [a, b)","articleBody":"**Describe the bug**\r\n\u003e Produces random floating-point values i, uniformly distributed on the interval [a, b)\r\n\r\n*[cppreference.com](https://en.cppreference.com/w/cpp/numeric/random/uniform_real_distribution)*\r\n\r\nThe below code sample demonstrates how a default-constructed `uniform_real_distribution\u003cfloat\u003e` (a=0, b=1) generates a `1.0f` if provided a random number with all bits set:\r\n\r\n**Command-line test case**\r\n```\r\n#include \u003ccassert\u003e\r\n#include \u003ccstdint\u003e\r\n#include \u003climits\u003e\r\n#include \u003crandom\u003e\r\n\r\nstruct max_rng\r\n{\r\n\tusing result_type = std::uint32_t;\r\n\tresult_type min() const { return 0; }\r\n\tresult_type max() const { return std::numeric_limits\u003cresult_type\u003e::max(); }\r\n\tresult_type operator()() { return max(); }\r\n};\r\n\r\nint main()\r\n{\r\n\tmax_rng rng;\r\n\tstd::uniform_real_distribution\u003cfloat\u003e iid;\r\n\r\n\tassert(iid(rng) \u003c 1.0f);\r\n\r\n\treturn 0;\r\n}\r\n```\r\n\r\n**Expected behavior**\r\nRegardless 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.\r\n\r\n**STL version**\r\nMicrosoft Visual Studio Community 2019\r\nVersion 16.6.4\r\n\r\n**Additional context**\r\nThe error seems to originate from [`generate_canonical`](https://github.com/microsoft/STL/blob/c10ae01b4d9508eed9d5f059a120ee7223b6ac12/stl/inc/random#L261), which, when passed in the above code, simplifies down to:\r\n\r\n```\r\nreturn (float) UINT_MAX / (UINT_MAX + 1.0f);\r\n```\r\nwhich, 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:\r\n```\r\n// @rnd: uniformly distributed 32bit unsigned int.\r\nreturn (rnd \u003e\u003e 8) / 164233216.0f\r\n```\r\nwhich 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.\r\n\r\nAlso tracked by DevCom-110322 and Microsoft-internal VSO-253526 / [AB#253526](https://devdiv.visualstudio.com/0bdbc590-a062-4c3f-b0f6-9383f67865ee/_workitems/edit/253526) .\r\n","author":{"url":"https://github.com/denniskb","@type":"Person","name":"denniskb"},"datePublished":"2020-07-22T00:13:58.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":7},"url":"https://github.com/1074/STL/issues/1074"}