<random>: discrete_distribution can return out-of-bound result

[statementreply]

Describe the bug

discrete_distribution should return an integer i such that 0 <= i < n. However, with certain parameters it can return n rarely.

This can lead to UB in piecewise_constant_distribution, piecewise_linear_distribution and user code that use the result of discrete_distribution for array index.

Command-line test case

C:\Users\He\source\test>type discrete_distribution.cpp
#include <iostream>
#include <random>

using namespace std;

int main() {
    constexpr int bound = 100'000'019;
    discrete_distribution<> dist(bound, 0, 1, [](double) { return 1.0; });
    mt19937 rng;
    rng.discard(862'454'404);

    for (long long i = 0; i < 1'000'000'000'000'000'000; ++i) {
        const auto value = dist(rng);
        if (!(0 <= value && value < bound)) {
            cout << "test failure\n";
            cout << "expected an integer within [0, " << bound << "), got " << value << "\n";
            break;
        }
    }
}

C:\Users\He\source\test>cl /EHsc /W4 /WX /O2 discrete_distribution.cpp
用于 x64 的 Microsoft (R) C/C++ 优化编译器 19.27.29009.1 版
版权所有(C) Microsoft Corporation。保留所有权利。

discrete_distribution.cpp
Microsoft (R) Incremental Linker Version 14.27.29009.1
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:discrete_distribution.exe
discrete_distribution.obj

C:\Users\He\source\test>.\discrete_distribution.exe
test failure
expected an integer within [0, 100000019), got 100000019

STL version

Microsoft Visual Studio Community 2019 Preview
版本 16.7.0 Preview 3.1