问题描述
有时候,即使我正确使用了Mersenne Twister引擎并迭代它,我仍然会从均匀分布中获得相同的随机数。我知道引擎可能状态的数量是有限的,产生的随机值的数量也是有限的,但现在并非如此。
使用boost的实现,在范围[0;1e7)上生成1百万个均匀分布的随机值。这意味着可能的值要比所需的随机值多得多。然而,我经常获得相同的值,有时在这个范围内超过100次。这是怎么可能的?
代码
提供了一个简单的代码以重现这种情况。在两个平台上我都遇到了同样的问题:
- MSVS 2019与boost-random:x64-windows 1.71.0,以及
- g++(Ubuntu 5.4.0-6ubuntu1〜16.04.12)5.4.0 20160609与libboost-dev 1.58.0.1ubuntu1
#include <iostream>
#include <chrono>
#include <boost/random/mersenne_twister.hpp> // random number generator
#include <boost/random/uniform_real_distribution.hpp> // uniform distribution generator
using namespace std;
int main()
{
size_t seed = static_cast<int> (std::chrono::system_clock::now().time_since_epoch().count());
cout << "seed = " << seed << endl;
boost::random::mt19937 engine(seed); // the random number generator engine
boost::random::uniform_real_distribution<double> u(0, 1e7); // uniformly distributed double values on the range [0; 1e7)
cout.precision(20);
vector<double> history; // stores the generated values for comparison
for (size_t i = 0; i < 1e6; ++i)
{
history.push_back(u(engine));
for (size_t j = 0; j < i; ++j)
if (history[i] == history[j])
cout << "Equal values ("<< history[i] <<") at ID = " << i << " and " << j << endl;
}
}
问题
代码中产生相同值的是bug吗?还是boost本身存在问题?
对于我的任务来说,生成具有均匀分布的数字非常重要。找到相同值是最简单的测试之一,但还有许多其他测试,我确定我不想在像Boost这样的知名库上进行质量分析。我不想使用标准库,因为不能保证两个不同的编译器对于相同的种子值会产生相同的序列,但这是任务的要求。你能提出什么样的解决方案?
注意
如果将生成的值与std::random生成的值
进行比较,则可以看到奇怪的行为。例如,对于种子值4561565448989,从random::boost
生成的值如下:
1755586.0406719148159
3354420.976247638464 <--
3630764.0071026980877
3488445.2889673411846 <--
7920481.4555123448372
8773544.1024415194988 <--
标准库生成时
3354420.9766563926823 <--
3488445.2898126943037 <--
8773544.1042856499553 <--
...
换句话说,Boost序列中每秒生成的值与标准库实现中对应的值非常接近。当两个boost序列中的值相同时,标准库序列中的值不相等,但是非常接近。这种相似性适用于MSVS和g++编译器,它们有权在Mersenne Twister和分布上具有不同的实现。
更新
种子不好?
有人建议可能是种子值不好导致了这种现象,因为只有使用 size_t
,才能生成 2 ^ 64
个不同的初始状态。更糟糕的是,我们的生命是很短暂的,可能的时间值甚至更少。尽管如此,这并不能解释为什么会从不同的状态多次生成相同的数字。毕竟,引擎只被初始化一次,所以我从一个64位子集中选择了一个状态,即所有可能状态的子集。如果我多次初始化引擎,并且在不同(但不够不同)初始化的引擎序列中找到相同的值,则可能是种子不好的原因。
是分布生成器
如果使用标准MT引擎,但使用boost的分布,问题仍然存在。但是,如果使用boost中的引擎和标准分布,则问题消失了。问题是,正如Peter指出的那样,均匀分布取决于平台,而我使用boost。一些统计数据
我对分布进行了一点分析。使用相同的 boost :: random :: mt19937 engine
,但是使用boost或std的 uniform_real_distribution u(0,1)
之一,我生成值对并调查它们的差异,并绘制它们的相关积分(x),即两个值距离小于的概率。由于[U] [0; 1)是一个1D域,因此I(x)对于小的x值起始为线性函数(并趋近于1)。结果显示在下图中。
该图表表明,boost实现的分布不仅具有偏差,而且只有4种可能的距离值,而已知<代码> double 更密集,而std确实产生了更大的距离值谱。
错误还是不是错误?删除的答案
一篇被删除的回答建议改进种子值,但目前发现这不是问题的根源。从那时起,我在boost的github上发布了此问题,但仍然不清楚问题所在。它可能是boost中的一个bug,但即使如此,此SO源也可以帮助他人识别其分布式生成器中的问题。