| Issue |
241897
|
| Summary |
[libc++] binomial_distribution returns values outside [0, t] or never returns when t is the largest value of IntType
|
| Labels |
libc++
|
| Assignees |
|
| Reporter |
0z5a
|
`std::binomial_distribution<IntType>(t, p)` misbehaves when `t == std::numeric_limits<IntType>::max()`. [rand.dist.bern.bin] only requires `0 <= t` and `0 <= p <= 1`, so this `t` is valid, and every result must lie in `[0, t]`.
```cpp
#include <iostream>
#include <limits>
#include <random>
int main() {
std::mt19937 g;
const short t = std::numeric_limits<short>::max();
std::binomial_distribution<short> d(t, 0.9999);
int out_of_range = 0;
short lowest = t;
for (int i = 0; i < 100000; ++i) {
short v = d(g);
if (v < 0 || v > t)
++out_of_range;
if (v < lowest)
lowest = v;
}
std::cout << "out_of_range=" << out_of_range << " lowest=" << lowest << '\n';
}
```
With libc++ (clang 15 through trunk) this prints `out_of_range=1917 lowest=-32767`. With libstdc++ it prints `out_of_range=0 lowest=32753`.
For `binomial_distribution<int>(INT_MAX, 0.5)`, a few draws return `0` (the expected mean is about 1073741823), and then a draw never finishes. UBSan reports:
```
binomial_distribution.h:105:44: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'
```
`unsigned`, `long long` and `unsigned long long` overflow at the same place.
There are two overflows in `libcxx/include/__random/binomial_distribution.h`:
- The `param_type` constructor computes the mode as `(__t_ + 1) * __p_`. The `__t_ + 1` is evaluated in `result_type`.
- `operator()` does `++__ru; if (__ru <= __pr.__t_)`. When the upward search reaches `__ru == t`, the increment overflows. For `short` the value wraps to a negative number, which passes the `<= t` check and is returned.
The proposed fix computes the mode in floating point and stops incrementing `__ru` at `t`. Results for every other `t` below 2^53 are unchanged. The test goes in `rand.dist.bern.bin/eval.pass.cpp`.
A fix with a regression test is ready. I can open a pull request for it.
Assisted-by: Claude (claude-opus-5-5). I reviewed the change and this text.
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs