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

Reply via email to