随机引擎差异

Question

在C++ 11标准规定一个数用于随机数生成不同的引擎的:linear_congruential_engine,mersenne_twister_engine,subtract_with_carry_engine等.显然,这是旧的用法的一个很大的变化std::rand.

显然,这些引擎(至少有一些)的主要好处之一是大大增加了周期长度(它的名称已经内置std::mt19937).

但是,引擎之间的差异不太明显.不同发动机的优点和缺点是什么？应该何时使用另一个？通常应该首选合理的默认值吗？

Answer 1

从下面的解释来看,线性引擎似乎更快但随机性更小,而Marsenne Twister具有更高的复杂性和随机性.减去携带随机数引擎是对线性引擎的改进,并且它更加随机.在最后的参考文献中,Mersenne Twister的复杂性高于带有减法的随机数引擎

线性同余随机数引擎

伪随机数生成器引擎,用于生成无符号整数.

这是标准库中最简单的生成器引擎.它的状态是一个整数值,具有以下转换算法:

x =(ax + c)mod m

其中x是当前状态值,a和c是它们各自的模板参数,如果m大于0,则m是其各自的模板参数,否则为numerics_limits :: max()加1.

它的生成算法是状态值的直接副本.

这使得它在处理和存储器消耗方面成为非常高效的发生器,但产生具有不同程度的串行相关性的数字,这取决于所使用的特定参数.

linear_congruential_engine生成的随机数的周期为m. http://www.cplusplus.com/reference/random/linear_congruential_engine/

Mersenne Twister随机数引擎

伪随机数生成器引擎,在闭区间[0,2 ^ w-1]中生成无符号整数.

该引擎使用的算法经过优化,可以计算大量数字(例如在蒙特卡罗实验中),在该范围内几乎均匀分布.

引擎具有n个整数元素的内部状态序列,其填充有在构造时生成的伪随机序列或通过调用成员函数种子.

内部状态序列成为n个元素的来源:当状态提前时(例如,为了产生新的随机数),引擎通过在混合位上使用xor mask a扭转当前值来改变状态序列由参数r确定的来自该值和m个元素的值(详见operator()).

产生的随机数是这些扭曲值的缓和版本.回火是由参数u,d,s,b,t,c和l定义的一系列移位和xor运算,应用于选定的状态值(参见operator()).

由mersenne_twister_engine生成的随机数具有相当于mersenne数2 ^((n-1)*w)-1的周期.http://www.cplusplus.com/reference/random/mersenne_twister_engine/

减去携带随机数引擎

伪随机数生成器引擎,用于生成无符号整数.

该引擎使用的算法是滞后的斐波纳契生成器,具有r个整数元素的状态序列,加上一个进位值.http://www.cplusplus.com/reference/random/subtract_with_carry_engine/

如果使用加法或减法,滞后Fibonacci生成器的最大周期为(2k - 1)*^(2M-1).LFG的初始化是一个非常复杂的问题.LFG的输出对初始条件非常敏感,并且除非特别小心,否则最初可能出现统计缺陷,但也会在输出序列中周期性地出现统计缺陷.LFG的另一个潜在问题是它们背后的数学理论是不完整的,因此有必要依靠统计检验而不是理论性能. http://en.wikipedia.org/wiki/Lagged_Fibonacci_generator

最后:选择使用哪种引擎需要进行多种权衡:线性同余引擎速度适中,对状态的存储要求非常小.即使在没有高级算术指令集的处理器上,滞后的Fibonacci发生器也非常快,代价是更大的状态存储和有时不太理想的频谱特性.梅森捻线机速度较慢且具有较大的状态存储要求,但正确的参数具有最长的非重复序列,具有最理想的光谱特性(对于给定的理想定义).在http://en.cppreference.com/w/cpp/numeric/random中

Answer 2

我认为重点是随机生成器具有不同的属性,这可以使它们更适合或不适合给定的问题.

• 的周期长度是属性之一.
• 随机数的质量也很重要.
• 发电机的性能也是一个问题.

根据您的需要,您可能需要一台发电机或另一台发电机.例如,如果您需要快速随机数但不关心质量,那么LCG可能是一个不错的选择.如果你想要更高质量的随机数,Mersenne Twister可能是更好的选择.

为了帮助你做出选择,也有一些标准测试和结果(我绝对喜欢的表第29页文章).

编辑:从论文,

1. LCG(LCG(***)论文中)系列是最快的发电机,但质量最差.
2. Mersenne Twister(MT19937)有点慢,但产生更好的随机数.
3. 带有进位的减法(SWB(***)我认为)速度较慢,但​​经过充分调整后可以产生更好的随机属性.

Answer 3

由于其他答案忘记了ranlux,这是AMD开发人员最近将其移植到OpenCL的一个小记录:

https://community.amd.com/thread/139236

RANLUX也是极少数(我实际上唯一知道的)PRNG之一,它有一个基础理论解释为什么它产生"随机"数字,以及为什么它们是好的.事实上,如果理论是正确的(并且我不知道有人对此提出异议),那么最高级别的RANLUX会产生完全去相关的数字,直到最后一点,只要我们保持良好状态就没有长距离相关性低于期间(10 ^ 171).大多数其他发电机可以说很少关于它们的质量(如Mersenne Twister,KISS等).它们必须依靠通过统计测试.

欧洲核子研究中心的物理学家是这个PRNG的粉丝.'努夫说.