随机数计算法比较,更好的随机数对于程序是否真的值得。
随机数计算法比较,更好的随机数对于程序是否真的值得。
本次,我们将评测四种随机数生成法
测试语言为C++
测试有不严谨的地方欢迎提出。
本文仅仅发布于云海天
下面是他们时间表现
名称 | 生成(1 imes 10^9)个随机数耗时(ms) |
---|---|
库函数rand耗时 | 8634 |
mt19937 | 8176 |
xorshift32耗时 | 6724 |
modrand耗时 | 6116 |
算法介绍
库函数rand
这个不用多说,cstdlib里的库函数。
用的就是LCG(linear congruential generator)算法
基于(X(n+1) = (a * X(n) + c) mod m)这样的公式
下面的modrand就是手写实现的这种算法。
mt19937
也就是Mersenne Twister MT19937(马特赛特旋转演算法)的实现。
基于有限二进制字段上的矩阵线性再生。可以快速产生高质量的伪随机数,修正了古老随机数产生算法的很多缺陷。
转载自百度百科:
Mersenne Twister算法的原理:Mersenne Twister算法是利用线性反馈移位寄存器(LFSR)产生随机数的,LFSR的反馈函数是寄存器中某些位的简单异或,这些位也称之为抽头序列。一个(n)位的LFSR能够在重复之前产生(2^n-1)位长的伪随机序列。只有具有一定抽头序列的LFSR才能通过所有(2^n-1)个内部状态,产生(2^n – 1)位长的伪随机序列,这个输出的序列就称之为m序列。为了使LFSR成为最大周期的LFSR,由抽头序列加上常数1形成的多项式必须是本原多项式。一个n阶本原多项式是不可约多项式,它能整除(x^(2*n-1)+1)而不能整除(x^d+1),其中d能整除(2^n-1)。例如((32,7,5,3,2,1,0))是指本原多项式(x^32+x^7+x^5+x^3+x^2+x+1),把它转化为最大周期LFSR就是在LFSR的第(32,7,5,2,1)位抽头。利用上述两种方法产生周期为(m)的伪随机序列后,只需要将产生的伪随机序列除以序列的周期,就可以得到((0,1))上均匀分布的伪随机序列了。
Mersenne Twister有以下优点:随机性好,在计算机上容易实现,占用内存较少(mt19937的C程式码执行仅需(624)个字的工作区域),与其它已使用的伪随机数发生器相比,产生随机数的速度快、周期长,可达到2^19937-1,且具有623维均匀分布的性质,对于一般的应用来说,足够大了,序列关联比较小,能通过很多随机性测试。
xorshift32
int xorshift32()
{
static int x(13147);
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return x;
}
是一个比较复杂的数论问题,作者也不会。
modrand
看代码就知道是什么原理了
unsigned int modrand()
{
static int seed(13147);
seed = (seed * 31 + 13) % ((1 << 31) - 1);
return seed;
}
实际表现
上面的算法,有的实现快,但是生成的质量不一定高,有的质量高,生成就更慢。
所以实际表现到底怎么样呢?
我将对下面的项目进行测试
序号 | 项目名 |
---|---|
1 | FHQ_Treap实现普通平衡树(数据加强版) |
上面两个应该是随机函数比较常见的应用了。
结果
FHQ_Treap(Rand生成速度将影响总时间,而随机数的质量将影响树高,也会影响总时间)
名称 | 耗时(s) |
---|---|
库函数rand耗时 | 8.33s |
mt19937 | 8.72s |
xorshift32耗时 | 8.34s |
modrand耗时 | 8.72s |
可以发现rand本身就够用了,除非有特殊要求没必要换用其他的函数。更没必要自己手写。