在阅读如何使用std :: rand时,我在cppreference.com上找到了这段代码
int x = 7;
while(x > 6)
x = 1 + std::rand()/((RAND_MAX + 1u)/6); // Note: 1+rand()%6 is biased
右边的表达有什么问题？尝试过,它完美无缺.
Pet*_*ker 136
有两个问题rand() % 6(1+不影响任何一个问题).
首先,正如几个答案所指出的,如果低位rand()不均匀,则余数运算符的结果也不均匀.
其次,如果产生的不同值的数量rand()不是6的倍数,则余数将产生比高值更低的值.即使rand()返回完美分布的值,也是如此.
作为一个极端的例子,假装rand()在该范围内产生均匀分布的值[0..6].如果查看这些值的余数,则rand()返回范围内的值时[0..5],余数会在范围内生成均匀分布的结果[0..5].当rand()返回6时,rand() % 6返回0,就好像rand()已经返回0.所以你得到的分布是任何其他值的两倍0.
第二个是真正的问题rand() % 6.
避免该问题的方法是丢弃会产生非均匀重复的值.你计算出小于或等于6的最大倍数RAND_MAX,并且每当rand()返回一个大于或等于该倍数的值时,你就会拒绝它并再次调用`rand(),这是需要的次数.
所以:
int max = 6 * ((RAND_MAX + 1u) / 6)
int value = rand();
while (value >= max)
value = rand();
这是有问题的代码的不同实现,旨在更清楚地显示正在发生的事情.
Bat*_*eba 19
这里有隐藏的深度:
使用小的u在RAND_MAX + 1u.RAND_MAX被定义为一种int类型,并且通常是最大的类型int.在您遇到类型溢出的情况下,行为RAND_MAX + 1将是未定义的signed.写入1u强制类型转换RAND_MAX为unsigned,从而避免溢出.
% 6 can的使用(但在std::rand我所见过的 每一个实现中都没有)引入任何额外的统计偏差,超出了所提出的替代方案.这种情况下% 6危险的情况是数字生成器具有低阶位的相关平台,例如rand,我认为,在20世纪70年代将高位和低位翻转为"最终"的相当着名的IBM实现(在C中)繁荣".进一步的考虑是6是非常小的参考.RAND_MAX,如果RAND_MAX不是6的倍数,那么将会产生最小的影响,这可能不是.
总而言之,这些天,由于其易处理性,我会使用% 6.除了发电机本身引入的统计异常之外,它不太可能引入任何统计异常.如果您仍然有疑问,请测试您的生成器,看它是否具有适合您的用例的统计属性.
Squ*_*age 13
这个示例代码说明std::rand了传统货物崇拜balderdash的情况,每次看到它时都应该让你的眉毛升起.
这里有几个问题:
合同人们通常认为 - 即使是那些不知道更好的穷人倒霉灵魂,也不会用这些术语来思考 - 是0,1,2,......中整数均匀分布的rand样本,每个调用产生一个独立的样本.RAND_MAX
第一个问题是假定的合同,每次调用中独立的统一随机样本,实际上并不是文档所说的 - 实际上,实现历史上甚至无法提供最独立的模拟. 例如,C99§7.20.2.1' rand函数'说,没有详细说明:
该
rand函数计算0到0范围内的伪随机整数序列RAND_MAX.
这是一个毫无意义的句子,因为伪随机性是函数(或函数族)的属性,而不是整数,但这并不能阻止ISO官僚滥用语言.毕竟,唯一会被它感到不安的读者比阅读文档要好得多rand,因为他们害怕脑细胞腐烂.
C中典型的历史实现如下:
static unsigned int seed = 1;
static void
srand(unsigned int s)
{
seed = s;
}
static unsigned int
rand(void)
{
seed = (seed*1103515245 + 12345) % ((unsigned long)RAND_MAX + 1);
return (int)seed;
}
这具有令人遗憾的特性,即使单个样本可以均匀地分布在均匀随机种子下(取决于具体值RAND_MAX),它在连续的呼叫之后在偶数和奇数整数之间交替.
int a = rand();
int b = rand();
表达式(a & 1) ^ (b & 1)产生1,概率为100%,而在偶数和奇数整数上支持的任何分布上的独立随机样本不是这种情况.因此,出现了一种货币崇拜,人们应该抛弃低阶位来追逐难以捉摸的"更好随机性"的野兽.(剧透警报:这不是一个技术术语.这表明你正在阅读的散文或者不知道他们在谈论什么,或者认为你是无知的,必须屈服于.)
第二个问题是,即使每次调用独立于0,1,2,...... 的均匀随机分布进行采样RAND_MAX,结果rand() % 6也不会像0,1,2,3,4,5一样均匀分布.滚动,除非RAND_MAX与-1模6一致. 简单的反例:如果RAND_MAX= 6,则从rand(),所有结果具有相等的概率1/7,但从中rand() % 6,结果0具有概率2/7而所有其他结果具有概率1/7 .
正确的方法是使用拒绝采样: 重复绘制一个独立的均匀随机样本,s从0,1,2,... RAND_MAX,并拒绝(例如)结果0,1,2,...,((RAND_MAX + 1) % 6) - 1- 如果你得到其中一个那些,重新开始; 否则,收益率s % 6.
unsigned int s;
while ((s = rand()) < ((unsigned long)RAND_MAX + 1) % 6)
continue;
return s % 6;
这样rand(),我们接受的结果集合可以被6整除,并且每个可能的结果s % 6都是通过相同数量的可接受结果获得的rand(),所以如果rand()是均匀分布则那么s.试验数量没有限制,但预期数量小于2,成功概率随试验次数呈指数增长.
您拒绝哪些结果的选择rand()并不重要,前提是您将相同数量的结果映射到6以下的每个整数.cppreference.com上的代码做出了不同的选择,因为上面的第一个问题 - 没有任何保证输出的分布或独立性,rand()实际上低阶位表现出的模式并不"看起来足够随机"(更不用说下一个输出是前一个输出的确定性函数).
为读者练习:证明cppreference.com上的代码在掷骰子上产生均匀分布,如果rand()在0,1,2,......上产生均匀分布RAND_MAX.
为读者练习:为什么你更喜欢拒绝一个或另一个子集？在这两种情况下,每次试验需要什么计算？
第三个问题是种子空间太小,即使种子均匀分布,对手掌握了你的程序和一个结果而不是种子的对手可以很容易地预测种子和随后的结果,这使得它们看起来不那么毕竟是随机的. 因此,甚至不要考虑将其用于加密.
你可以std::uniform_int_distribution使用适当的随机设备和你最喜欢的随机引擎,比如流行的Mersenne twister std::mt19937与你四岁的堂兄一起玩骰子,你可以选择花哨的过度工程路线和C++ 11的课程,但即使这样也不会适合生成加密密钥材料 - 而Mersenne twister也是一个可怕的太空猪,因为一个数千字节的状态会对你的CPU缓存造成严重的破坏性设置时间,所以即使对于例如并行的蒙特卡罗模拟也很糟糕可重现的子计算树; 它的受欢迎程度可能主要来自其吸引人的名字.但你可以像玩这个例子一样用它来玩玩具骰子!
另一种方法是使用具有小状态的简单加密伪随机数发生器,例如简单的快速密钥擦除PRNG,或者如果您有信心则使用诸如AES-CTR或ChaCha20之类的流密码(例如,在蒙特卡罗模拟中自然科学研究)如果国家受到损害,对预测过去的结果没有不利后果.