C++ uniform_int_distribution总是在第一次调用时返回min()

Question

在至少一个实施标准库,的第一次调用std::uniform_int_distribution<>并不能返回一个随机值,而是分布的最小值.也就是说,给出代码:

default_random_engine engine( any_seed() );
uniform_int_distribution< int > distribution( smaller, larger );
auto x = distribution( engine );
assert( x == smaller );

...... x其实会smaller为任何值any_seed(),smaller或larger.

要在家中玩,您可以尝试在gcc 4.8.1中演示此问题的代码示例.

我相信这是不正确的行为？如果它是正确的行为,为什么随机分布会返回这个明显非随机的值？

Answer 1

观察到的行为的解释

这是如何uniform_int_distribution随机比特映射到数字如果可能结果的范围比该RNG产生数的范围更小:

const __uctype __uerange = __urange + 1; // __urange can be zero
const __uctype __scaling = __urngrange / __uerange;
const __uctype __past = __uerange * __scaling;
do
  __ret = __uctype(__urng()) - __urngmin;
while (__ret >= __past);
__ret /= __scaling;

在哪里__urange是larger - smaller和__urngrangerng可以返回的最大值和最小值之间的差异.(来自libstdc ++ 6.1中bits/uniform_int_dist.h的代码)

在我们的例子中,rng default_random_engine是a minstd_rand0,它产生__scaling == 195225785你测试的范围[0,10].因此,如果rng() < 195225785,分布将返回0.

minstd_rand0返回的第一个数字是

(16807 * seed) % 2147483647

(在哪里seed == 0调整到1顺便说一句).因此,我们可以看到,minstd_rand0数量小于11615 的种子产生的第一个值将与uniform_int_distribution< int > distribution( 0, 10 );您使用的产生0 .(我个人的错误.)))

你提到了更大的种子消失的问题:一旦种子变得足够大以实际使mod操作做某事,我们不能简单地通过除法将整个范围的值分配给相同的输出,因此结果看起来会更好.

这是否意味着(libstdc ++的impl)<random>被打破了？

不会.你通过总是选择它来引入一个应该是随机32位种子的显着偏差.在结果中出现的这种偏见并不令人惊讶或邪恶.对于随机种子,即使你的minstd_rand0意志也会产生相当均匀随机的第一个值.(虽然之后的数字序列不具有很好的统计质量.)

我们能做些什么呢？

案例1:您想要随机数的高统计质量.

为此,你使用更好的rng mt19937和种子整个状态空间.对于Mersenne Twister来说,这是624个32位整数.(作为参考,这是我试图在答案中提供一些有用的建议.)

案例2:你真的只想使用那些小种子.

我们仍然可以从中获得不错的结果.问题是伪随机数发生器通常在某种程度上依赖于它们的种子.为了解决这个问题,我们丢弃了足够的数字,让最初相似的输出序列发散.所以如果你的种子必须很小,你可以像这样初始化你的rng:

std::mt19937 rng(smallSeed);
rng.discard(700000);

至关重要的是,你要使用像Mersenne Twister这样的好品牌.我不知道有什么方法可以从种子不好的地方获得合适的价值minstd_rand0,例如看到这个火车残骸.即使播种得当,a的统计特性mt19937也是优越的.

关于大型国家空间或有时听到的缓慢生成的担忧通常在嵌入式世界之外无关紧要.根据boost和cacert.at,MT的速度甚至更快minstd_rand0.

你仍然需要做丢弃技巧,即使你的结果在没有肉眼的情况下看起来很好.它在我的系统上只需不到一毫秒,而且你不经常播种rng,所以没有理由不这样做.

请注意,我无法对您需要的丢弃数量给出一个明确的估计,我从这个答案中获取了这个值,它将本文与理性相关联.我现在没时间完成这项工作.