随机数计算法比较,更好的随机数对于程序是否真的值得。

随机数计算法比较,更好的随机数对于程序是否真的值得。

随机数计算法比较,更好的随机数对于程序是否真的值得。

本次,我们将评测四种随机数生成法
测试语言为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本身就够用了,除非有特殊要求没必要换用其他的函数。更没必要自己手写。

hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » 随机数计算法比较,更好的随机数对于程序是否真的值得。