TL; DR:default_random_engine
无法为您提供任何保证。如果要数字随机,请使用mt19937_64
。如果要生成与安全性相关的随机性(键,IV,盐,密码等),请找到从random_device
播种的CSPRNG或使用random_device
。有关default_random_engine
的g++
行为的有趣分析,请参见下文。
default_random_engine
是实现定义的
如注释中所述,default_random_engine
具有实现定义的行为,您可能根本不应该使用它。实现定义的意味着,例如,可以免费使用著名的XKCD rng:
class default_random_engine
{
public:
using result_type = uint32_t;
result_type min() const
{
return 1;
}
result_type max() const
{
return 6;
}
default_random_engine(int) {}; // we don’t care about the argument
result_type operator()() const
{
return 4; // chosen by fair dice roll
// guaranteed to be random
}
};
default_random_engine
不能很好地用于彼此靠近的种子
但是,实际上看起来很简单,
default_random_engine
(在GNU libstdc ++中使用)与
time(0)
当前产生的种子和/或使用
uniform_int_distribution<int>(1, 6)
采样的分辨率有很大的偏差。尝试在同一程序中一次生成多个随机数。您将找到类似以下的输出:
6 6 6 4 6 2 2 3
,
6 3 2 1 4 6 3 3
,…。简而言之,
default_random_engine
没有任何保证,并且对于任何目的来说都是非常糟糕的RNG(显然,甚至是关于随机API的教导,因为在生成带有UNIX时代时间戳的单个diceroll时,它似乎不是随机的!)。
所以我跑了数字。通过一个小程序(见下文),我计算了在
default_random_engine
和
mt19937_64
生成的第一个骰子掷骰数的概率分布为6,在种子范围内绘制。这与g ++(Debian 6.1.1-11)6.1.1 20160802和libstdc ++ 6.1.1-11一起使用。
该图显示了用X轴上的种子初始化相应的随机引擎后,在第一次绘制中用
std::uniform_int_distribution<int> (1,6)
获得6的概率。此外,当前的Unix时间绘制为垂直黑线(仅在图表的顶部范围内可见)。如您所见,我们目前处于整数分布很有可能(100%)使用
default_random_engine
输出6作为第一个数字的范围内。相反,
mt19937_64
非常接近预期的⅙概率。直方图的bin大小为10000(或从unix-epoch开始的秒数,约为2.8小时)。
同样,在整个测试范围(0..4e9-1)中,
default_random_engine
实际上将第一个数字6产生,概率约为1/3。处理彼此“接近”(±1000)的种子真的很不好。
结论
因此,在某种程度上,
time(0)
是罪魁祸首,因为它变化缓慢。而且,(使用的标准库)Code :: Blocks是罪魁祸首,因为它们的
default_random_engine
很烂。适当的RNG不应在如此大的种子范围内偏向特定结果。只需使用适当的RNG,不要尝试使
default_random_engine
正常运行,这不能保证可在编译器和标准库之间移植。
如果需要出于数字目的的随机数(例如游戏物理模拟),请使用C ++ 11标准提供的数字合理的随机数引擎之一(例如提到的
mt19937_64)。
如果您需要随机数来进行任何与安全相关的操作(生成密码,盐,用于加密的IV,密钥等),请不要使用mt19937_64,而应使用直接使用
std::random_device
或
std::random_device
作为种子的CSPRNG。
另一个需要注意的问题是,由于本教程是针对游戏开发的:网络开始运行时,您实际上可能需要平台独立的行为。在这种情况下,选择具有特定参数的特定RNG引擎对于在客户端之间以及客户端与服务器之间实现可重现的结果至关重要。
资源
#include <array>
#include <cstdint>
#include <iostream>
#include <random>
#include <ctime>
void search()
{
static constexpr uint32_t SEARCH_MAX = 4000000000;
static constexpr uint32_t SEARCH_BLOCKS = 8;
static constexpr uint32_t SEARCH_BIN_SIZE = 10000;
static constexpr uint32_t SEARCH_BINS = SEARCH_MAX / SEARCH_BIN_SIZE;
static constexpr uint32_t SEARCH_STEP = 1;
static constexpr uint32_t OUTPUT_STEP = 1000000;
std::vector<uint32_t> histogram(SEARCH_BINS);
for (uint32_t &member: histogram) member = 0;
std::uniform_int_distribution<int> diceRoll(1, 6);
static constexpr uint32_t START = BLOCK * (SEARCH_MAX/SEARCH_BLOCKS);
static constexpr uint32_t END = START + SEARCH_MAX/SEARCH_BLOCKS;
for (uint32_t i = START; i < END; i+=SEARCH_STEP) {
rng_engine_to_use foo(i);
int roll = diceRoll(foo);
if (roll == 6) {
histogram[i/SEARCH_BIN_SIZE] += 1;
}
if (i % OUTPUT_STEP == 0) {
std::cerr << ((float)i / SEARCH_MAX * 100) << "% \r" << std::flush;
}
}
for (uint32_t i = START / SEARCH_BIN_SIZE; i < END/SEARCH_BIN_SIZE; ++i) {
std::cout << i*SEARCH_BIN_SIZE << " " << histogram[i] << std::endl;
}
}
int main()
{
search();
}
我将cc的块设置为0..7,以便为我的每个CPU内核构建一个版本,因为mt19937_64花费了相当多的时间来生成所有这些数字(我后来才意识到,当绘制在整个范围内,但是。)我分别用
#define
和
rng_engine_to_use
替换了
mt19937_64
并绘制了生成的直方图(如上所示)。