std::binomial_distribution 在某些输入下永远挂起

Question

std::binomial_distribution我在编译clang++（使用标准库）时遇到了一些奇怪的行为libstdc++。

考虑以下简单的程序：

#include <ctime>
#include <random>
#include <iostream>

unsigned binom(unsigned n, double p) {
  std::mt19937 e(time(NULL));
  std::binomial_distribution<unsigned> b(n, p);
  return b(e);
}

int main() {

  std::cout << "sample1=" << binom(1073741823, 0.51174692866744709) << "\n";
  std::cout << "sample2=" << binom(1073741824, 0.51174692866744709) << "\n";

}

该程序将输出一行 ( sample1=511766586\n)，然后无限期挂起。

我是否以某种方式调用了未定义的行为？无论 PRNG 返回什么，这似乎都会发生。无论我如何播种，我main都会坚持第二行。

Answer 1

binomial_distribution我调试了( _M_initialize, )的 GCC 实现operator()，这是我发现的：

由于无符号参数 (2^30) 的溢出，对象的n变量变为 ，因此相同对象的,和, ,发生相同的情况_M_s2__paraminf__s2s_M_s__u__a12__yoperator()

这导致了以下无限循环operator()

bool __reject;
do
{
    if (__u <= __a1)                        inf <= val --> false
    {
        [...]
    }
    else if (__u <= __a12)                  inf <= inf --> true
    {
        __reject = __y >= [...];            inf >= val --> true
    }
    __reject = __reject || [...];           true || bool --> true
    __reject |= [...];                      true | val --> truthy
}
while(__reject);

这是这些变量如何相等的（部分）回溯inf：

_M_t = n

_M_s2 = [...] * (1 + [double] / (4 * _M_t * [...]));
                                 ^^^^^^^^ overflow == 0
                     [double] / 0 == inf

__s2s = _M_s2 * _Ms2;

_M_s = [...] + __s2s * [...];


__u = __param._M_s * [...];

__a12 = [...] + __param._M_s2 * [...];

__y = __param._M_s2 * [...];

还值得注意的是，__d2x在__param对象中 isNaN以及有助于此过程的其他变量（我省略了其中的定义）具有（至少在这种情况下）有效值

一个可行的解决方案（直到错误修复）将使用std::binomial_distribution<unsigned long>(或uint64_t) 代替unsigned