精华内容
下载资源
问答
  • 2020-10-17 11:23:02

    我们知道C语言提供了随机数生成,另外Qt也提供了随机数的生成。

    比如C语言,生成0-19随机数,如下:

    srand(time(nullptr)); // 从1970-01-01 00:00:00到现在的秒数为随机数种子
    int val = rand() % 20;
    

    Qt生成0-19随机数,如下:

    qsrand(time(nullptr)); // 从1970-01-01 00:00:00到现在的秒数为随机数种子
    int val = qrand() % 20;
    

    一、高效随机数生成算法

    另外,在开源项目diskspd中发现一种更加高效的随机数生成算法,位于Common.h中。

    diskspd的github地址:https://github.com/microsoft/diskspd

    我对其进行了一点修改后,Random.h如下:

    #ifndef RANDOM_H
    #define RANDOM_H
    
    #include <QtGlobal>
    
    #ifdef WIN32 // windows
    #include <stdlib.h>
    #else // linux
    #define _rotl64(value, bits) ((value << bits) | (value >> (64 - bits))) // 64位变量value循环左移bits位
    #endif
    
    /**
     * @brief The Random class
     * 高效伪随机数生成器
     */
    class Random
    {
    public:
        Random(quint64 ulSeed = 0)
        {
            _ulState[0] = 0xf1ea5eed;
            _ulState[1] = ulSeed;
            _ulState[2] = ulSeed;
            _ulState[3] = ulSeed;
    
            for (quint32 i = 0; i < 20; i++)
            {
                rand64();
            }
        }
    
        inline quint64 rand64()
        {
            quint64 e = _ulState[0] - _rotl64(_ulState[1], 7);
            _ulState[0] = _ulState[1] ^ _rotl64(_ulState[2], 13);
            _ulState[1] = _ulState[2] + _rotl64(_ulState[3], 37);
            _ulState[2] = _ulState[3] + e;
            _ulState[3] = e + _ulState[0];
    
            return _ulState[3];
        }
    
        inline quint32 rand32()
        {
            return (quint32)rand64();
        }
    
    private:
        quint64 _ulState[4];
    };
    
    #endif // RANDOM_H
    

    二、3种随机数生成方式对比

    编写main.cpp测试代码,分别测试C、Qt以及我们实现的随机数算法,这3者的效率对比。

    #include <QCoreApplication>
    #include <QDebug>
    #include "Random.h"
    #include "CTimer.h"
    
    void test_c_random()
    {
        srand(time(nullptr));
    
        CTimer timer;
        timer.reset();  // 开始计时
    
        for (int i = 0; i < 200; i++)
        {
            int val = rand() % 20;
        }
    
        double elapsed = timer.end();  // 结束计时
        qDebug() << "elapsed time:" << elapsed << "us";
    }
    
    void test_qt_random()
    {
        qsrand(time(nullptr));
    
        CTimer timer;
        timer.reset();  // 开始计时
    
        for (int i = 0; i < 200; i++)
        {
            int val = qrand() % 20;
        }
    
        double elapsed = timer.end();  // 结束计时
        qDebug() << "elapsed time:" << elapsed << "us";
    }
    
    void test_custom_random()
    {
        Random random(time(nullptr));
    
        CTimer timer;
        timer.reset();  // 开始计时
    
        for (int i = 0; i < 200; i++)
        {
            int val = random.rand32() % 20;
        }
    
        double elapsed = timer.end();  // 结束计时
        qDebug() << "elapsed time:" << elapsed << "us";
    }
    
    int main(int argc, char *argv[])
    {
        QCoreApplication a(argc, argv);
    
        test_c_random();
        test_qt_random();
        test_custom_random();
    
        return a.exec();
    }
    

    编译,运行效果如下:

    在这里插入图片描述

    可以看到这个高效生成算法,比C/Qt,效率提升了79%

    当然,这三种,以及一般的随机数生成器都是产生的伪随机数。

    也就是只要随机数种子一样,那么该生成器产生的随机数值就是一样的。

    伪随机数都有周期,只是周期比较大而已,用在一般的场合下,也是没什么问题的。

    分享这个高效随机数生成器,若大家需要请自取。



    若对你有帮助,欢迎点赞、收藏、评论,你的支持就是我的最大动力!!!

    同时,阿超为大家准备了丰富的学习资料,欢迎关注公众号“超哥学编程”,即可领取。

    本文涉及工程代码,公众号回复:54Random,即可下载。

    在这里插入图片描述

    更多相关内容
  • 伪随机数生成算法

    千次阅读 2018-08-22 11:44:58
    伪随机数生成算法在计算机科学领域应用广泛,比如枪击游戏里子弹命中扰动、数据科学里对样本进行随机采样、密码设计、仿真领域等等,背后都会用到伪随机数生成算法。 说随机,那什么是随机呢? 随机 意味着不可...

    写在前面

    伪随机数生成算法在计算机科学领域应用广泛,比如枪击游戏里子弹命中扰动、数据科学里对样本进行随机采样、密码设计、仿真领域等等,背后都会用到伪随机数生成算法。

    骰子

    说随机,那什么是随机呢?随机意味着不可预测,没有任何规律。谈随机数,一定是在序列当中,单拿出一个数谈随机是没有意义的。给一个数字序列,如果能在其中发现规律可以预测或以一定概率(大于“猜”的概率)预测接下来的数,那么这个序列就不是随机的。

    在20世纪早期科学工作中就开始需要使用随机数,为了获取随机数,研究人员通过物理方式采集了成千上万的随机数,并发布给他人使用,比如RAND公司在1955年发布的《A Million Random Digits with 100,000 Normal Deviates》(百万乱数表)——亚马逊美国现在还有卖~。但是,通过物理方式采集“真”随机数并不高效,实时获取需要附加额外的随机数发生装置,而且获取速度缓慢、序列不可复现,如果将采集到随机数全保存下来则需要占用额外的存储空间,而且数量终究是有限的,于是大家开始寻求生成“伪”随机数的数学方法。伪随机数,顾名思义,即看起来是随机的但实际上不是,在不知其背后生成方式的情况下,生成的序列看上去毫无规律可言。

    本文源自个人兴趣通过查阅参考文献整理所得,再加上个人的理解,大部分图片来自WIKI。

    统计学检验

    如何判断一个序列是否够随机呢?伪随机数生成算法多种多样,总要分出个孰好孰差,如何对各自的随机性进行定量评估呢?主要有两类方式,其出发点都是试图定量评估序列中是否隐含某种规律或模式

    • 实证检验。给定一个随机序列而不告知其背后的生成方式,尝试对观测到的分布进行拟合,以预测后面的序列,或者查看其中是否具有某些统计规律,比如查看分布是否均匀、连续值的相关性、某些数出现位置的间隔分布是否有规律等等。具体有 χ 2 \chi ^2 χ2检验KS检验、Frequency test、Serial test等等。

    • 理论检验。直接分析生成器的理论性质(已知生成方式),生成器通常需要配置一些参数,不同的参数会影响生成序列的质量,比如考察不同参数对随机序列周期的影响。

    可在下一小节对理论检验一窥一二,但本文的重点不在于此,就不详细展开了,详细内容可见参考资料。

    线性同余法

    lin­ear con­gru­en­tial generator(LCG)线性同余法是最早最知名的伪随机数生成算法之一,曾被广泛应用,后逐渐被更优秀的算法替代,其通过如下递推关系定义:

    X n + 1 = ( a X n + c )   m o d   m X_{n+1} = (aX_n + c)\ mod \ m Xn+1=(aXn+c) mod m

    其中, X X X为伪随机序列,

    • m m m m &gt; 0 m &gt; 0 m>0,模数,显然其也是生成序列的最大周期
    • a a a 0 &lt; a &lt; m 0 &lt; a &lt; m 0<a<m,乘数
    • c c c 0 ≤ c &lt; m 0 \leq c &lt; m 0c<m,增量
    • X 0 X_0 X0 0 ≤ X 0 &lt; m 0 \leq X_0 &lt; m 0X0<m,种子点(起始值)

    c = 0 c = 0 c=0时,被称为multiplicative congruential generator (MCG),如果 c ≠ 0 c \neq 0 c̸=0,被称为mixed congruential generator。

    线性同余法的参数应该被小心选取,否则生成的序列将非常糟糕,比如当 a = 11 , c = 0 , m = 8 , X 0 = 1 a = 11, c = 0, m = 8, X_0=1 a=11,c=0,m=8,X0=1时,得到的序列是 3、1、3、1、3……从1960s开始使用IBM的RANDU算法,参数设置为 a = 65539 , c = 0 , m = 2 31 a = 65539, c = 0, m = 2^{31} a=65539,c=0,m=231,最终也被证明是糟糕的设计,因为 65539 = 2 16 + 3 65539 = 2 ^{16} + 3 65539=216+3,可进一步推导得

    X n + 2 = ( 2 16 + 3 ) X n + 1 = ( 2 16 + 3 ) 2 X n = [ 6 ( 2 16 + 3 ) − 9 ] X n = 6 X n + 1 − 9 X n X_{n+2} = (2^{16} + 3)X_{n+1} = (2^{16} + 3)^2 X_n = [6(2^{16} + 3) - 9]X_n=6X_{n+1}-9X_n Xn+2=(216+3)Xn+1=(216+3)2Xn=[6(216+3)9]Xn=6Xn+19Xn

    因为相邻3个数间存在这样的相关性,若将相邻3个数作为坐标绘制在3维坐标系里,会得到15个明显的平面

    RANDU

    可见,获得的序列并不是那么随机,而且没有均匀地填充整个空间。线性同余法的参数很重要,一些平台和运行时库中采用的参数如下

    Parameters in common use

    使用递推关系的方式带来了可复现的便利——只需要记住种子点就可以复现整个序列,而不需要去存储整个序列,但是带来的弊端就是相邻点之间的相关性,随意设置参数(像RANDU)可能让序列直落在几个稀疏的平面上,通常需要将 m m m选取的足够大,同时避开2的整数次幂。

    马特赛特旋转演算法

    Mersenne Twister 马特赛特旋转演算法,是1997年提出的伪随机数生成算法,其修复了以往随机数生成算法的诸多缺陷,可快速生成高质量的伪随机数,且经过了广泛的统计学检验,目前在各种编程语言和库中已普遍存在或作为默认的伪随机数发生器,被认为是更可靠的伪随机数发生器。下图截自python的官方文档:

    Python random

    Mersenne Twister生成随机数的过程比线性同余法要复杂得多,图示化如下:

    Mersenne Twister

    主要流程有3步是:

    1. 初始化 n n n个状态:根据给定的种子点 x 0 x_0 x0,通过移位、异或、乘法、加法等操作生成后续的 n − 1 n-1 n1个状态 x 1 x_1 x1 x n − 1 x_{n-1} xn1,bit位数为 w w w
    2. 生成伪随机数:根据当前状态,通过移位、与、异或操作生成随机数
    3. 更新 n n n个状态:每生成 n n n个随机数后,在生成下一个随机数前,更新状态

    具体参见伪代码(来自WIKI),如下:

    // Create a length n array to store the state of the generator
    int[0..n-1] MT
    int index := n+1
    const int lower_mask = (1 << r) - 1 // That is, the binary number of r 1's
    const int upper_mask = lowest w bits of (not lower_mask)
    
    // Initialize the generator from a seed
    function seed_mt(int seed) {
        index := n
        MT[0] := seed
        for i from 1 to (n - 1) { // loop over each element
            MT[i] := lowest w bits of (f * (MT[i-1] xor (MT[i-1] >> (w-2))) + i)
        }
    }
    
    // Extract a tempered value based on MT[index]
    // calling twist() every n numbers
    function extract_number() {
        if index >= n {
            if index > n {
              error "Generator was never seeded"
              // Alternatively, seed with constant value; 5489 is used in reference C code
            }
            twist()
        }
    
        int y := MT[index]
        y := y xor ((y >> u) and d)
        y := y xor ((y << s) and b)
        y := y xor ((y << t) and c)
        y := y xor (y >> l)
    
        index := index + 1
        return lowest w bits of (y)
    }
    
    // Generate the next n values from the series x_i 
    function twist() {
        for i from 0 to (n-1) {
            int x := (MT[i] and upper_mask)
                      + (MT[(i+1) mod n] and lower_mask)
            int xA := x >> 1
            if (x mod 2) != 0 { // lowest bit of x is 1
                xA := xA xor a
            }
            MT[i] := MT[(i + m) mod n] xor xA
        }
        index := 0
    }
    

    标准实现32bit版本称之为MT19937,参数设置如下:

    • ( w , n , m , r ) = ( 32 , 624 , 397 , 31 ) (w, n, m, r) = (32, 624, 397, 31) (w,n,m,r)=(32,624,397,31)
    • a = 9908 B 0 D F 16 a = \rm 9908B0DF_{16} a=9908B0DF16
    • ( u , d ) = ( 11 , F F F F F F F F 16 ) (u, d) = (11, \rm FFFFFFFF_{16}) (u,d)=(11,FFFFFFFF16)
    • ( s , b ) = ( 7 , 9 D 2 C 568 0 16 ) (s, b) = (7, \rm 9D2C5680_{16}) (s,b)=(7,9D2C568016)
    • ( t , c ) = ( 15 , E F C 6000 0 16 ) (t, c) = (15, \rm EFC60000_{16}) (t,c)=(15,EFC6000016)
    • l = 18 l = 18 l=18

    后记

    伪随机数生成算法有很多,远不止本文介绍的两种,还有middle-square method(1946)、Additive Congruential Method、xorshift(2003)WELL(2006,对Mersenne Twister的改进)等等,本文只是从中选取具有代表性的两种,可阅读参考文献了解更多。

    参考

    本文出自本人博客:伪随机数生成算法

    展开全文
  • 伪随机数生成算法及比较.pdf 分析了各种常见的伪随机数,并对其特征作了简要描述,并予以比较。
  • 一种Linux用户空间下的快速伪随机数生成算法.pdf
  • Mersenne Twister算法译为马特赛特旋转演算法,是伪随机数发生器之一,其主要作用是生成伪随机数。此算法是Makoto Matsumoto (松本)和Takuji Nishimura (西村)于1997年开发的,基于有限二进制字段上的矩阵线性再生。...
  • Redis源码中看伪随机数生成算法

    千次阅读 2015-04-05 14:51:09
    作者在该文件的注释中写道:这个伪随机数生成函数是从pysam源码中的drand48()派生过来的。关于pysam是什么项目,并不是重点,其实很多Unix系统中都存在drand48这个函数(SVr4,POSIX.1-2001),我们可在终端中man...

    导读

    ------------------------------------------------------------------------------------------------------------------------- -------------------------------------

            Redis源码中有一个rand.c的源文件,很明显这是一个和(伪)随机数有关的文件。细看该文件代码只有寥寥50行,不过涉及到的算法原理却不简单,读起来虽然有些晦涩,但对于深入理解48位空间中的伪随机数算法是不可多得的范本。作者在该文件的注释中写道:这个伪随机数生成函数是从pysam源码中的drand48()派生过来的。关于pysam是什么项目,并不是重点,其实很多Unix系统中都存在drand48这个函数(SVr4,POSIX.1-2001),我们可在终端中man一下drand48。

            可以看到在头文件stdlib.h中定义了一系列和随机数有关的函数,除drand48()外,还有erand48()、lrand48()、nrand48()等等。所谓的48指的是随机数种子的二进制位数。它们的主要操作使用的都是同一个随机数生成算法,但是后续的处理不同,比如drand48()、erand48()返回的是 [0.0, 1.0)之间的浮点型,而lrand48()和nrand48()返回的是[0, 2^31)之间的整数。rand.c文件中有一个重要的函数——redisLrand48()。虽然作者是受了drand48()源码的启发编写的该函数,但实际上redisLrand48()和lrand48()更像,拥有几乎一样的编程接口,并且设置相同的随机数种子,生成的伪随机数序列相同。

            继续读rand.c开头的注释,可以发现作者编写这个文件的目的是用于替换Lua中实现的math.random()函数。作者认为Lua随机数生成算法的默认实现中使用了libc的rand()函数,而libc的rand()并不能保证在设置了相同种子的情况下,不同平台能生成相同的随机数序列。因此作者重写这一文件,保证跨平台性。

    --------------------------------------------------------------------------------------------------------------------------------------------------------------

    算法原理

    线性同余方程

            该伪随机数生成算法使用了线性同余方程,顾名思义:所谓 “线性”,指的是自变量(方程中的x)和因变量(方程中的y)是线性关系;所谓 “同余”,表示它们与同一个数(比如m)相除,余数相同。可以表示为:y = f(x)%m 或 y = f(x) mod m 【f(x)是线性函数,即x的次数为1】
            在Linux中,通过lrand48的手册页,可以看到lrand48()所使用的线性同余方程的具体内容(Redis使用的是同一个方程):
    Xn+1 = (aXn + c) mod m, where n >= 0
    //默认情况下
    a = 0x5DEECE66D
    c = 0xB
    m = 2^48 
    X0、X1、X2……Xn就是伪随机数序列。它们每一个都要由上一个数字通过运算来生成。

    种子

            随机数生成算法中都有种子的概念,无论是普通的rand()还是lrand48()。我们前面多次提到 伪随机数这一术语,之所以说“伪”,是因为当种子确定之后,此后生成到随机数序列也就确定了。换句话说只要是相同的种子,生成的随机数序列总是固定的(相同的平台下),并非完全随机。
            通过上一小节中的线性同余方程,我们观察到随机数序列的生成受到X0、a、c的影响(m总是2^48,表示48位空间中的运算,所以这些函数后缀才会有48)。因而X0、a、c其本质就是种子。POSIX的lrand48()的实现中和Redis的实现中给这三个参数提供了相同默认值。但不同之处是POSIX标准提供了lcong48()函数来修改这三个参数的默认值,而Redis中仅仅能设置种子的方式(redisSrand48()函数)来修改X0(表示随机数序列的第一个数)的值,所以在Redis中真正的种子只有一个——X0.

    源码实现

    变量

            rand.c中定义了三个静态的全局变量:x、a、c 与线性同余方程中的参数相对应
    static uint32_t x[3] = { X0, X1, X2 }, a[3] = { A0, A1, A2 }, c = C;
    
    这里涉及到几个宏定义:
    #define X0	0x330E
    #define X1	0xABCD
    #define X2	0x1234
    #define A0	0xE66D
    #define A1	0xDEEC
    #define A2	0x5
    #define C	0xB
            可以看出数组a中的三个元素保存的就是线性同余方程中的常数 0x5DEECE66D的三个部分。注意的是a中每个元素是uint32_t类型,就是说4个字节,实际上我们把0x5DEECE66D拆成三个部分(0x5、0xDEEC、0xE66D),每个部分最多只占用了2个字节。另外要注意的是宏定义中的X0和前文(上一节)中的X0语义是不同的,这里的X0表示的是数组X默认初始化时的第一个元素的内容,而上一节中提到的X0表示的是第一个随机数,相当于本节中的X2*2^32 + X1*2^16 + X0。

    对外函数

            rand.c对外只提供了两个函数:
    • redisLrand48():返回一个随机数
    • redisSrand48():设置随机数种子
    另外还有一个静态函数next(),它是为redisLrand48()服务的,对外不可见。

    redisSrand48()函数

    void redisSrand48(int32_t seedval) {
        SEED(X0, LOW(seedval), HIGH(seedval));
    }
            设置随机数的种子,用到了宏函数SEED。看一下定义:
    #define SET3(x, x0, x1, x2)	((x)[0] = (x0), (x)[1] = (x1), (x)[2] = (x2))
    #define SEED(x0, x1, x2) (SET3(x, x0, x1, x2), SET3(a, A0, A1, A2), c = C)
            可以看成宏函数SEED进行了三个赋值操作,分别是给数组x、数组a和变量c。不过a和c赋的都是默认值,所以 SEED (X0, LOW (seedval), HIGH (seedval))实际进行的操作就是用X0(0x330E)、seedval的低16位,seedval的高16位分别赋值给x[0]、x[1]、x[2]。LOW和HIGH也是两个宏函数
    #define N	16 
    #define MASK	((1 << (N - 1)) + (1 << (N - 1)) - 1) //MASK=65535(16个二进制位1)
    #define LOW(x)	((unsigned)(x) & MASK)                //LOW(x)获得3x的低16位(2个字节)
    #define HIGH(x)	LOW((x) >> N)                         //HIGH(x)获得x的高16位(2个字节)

    注意上面所指的高16位和低16位指的是32位整型数据的高低。最终每次要保留的结果是48位的(存储在数组x[ ]中),它分为高16位(x[2])、中16位(x[1])和低16位(x[0])。不要混淆。

    redisLrand48()函数

    int32_t redisLrand48() {
        next();
        return (((int32_t)x[2] << (N - 1)) + (x[1] >> 1));
    }
            next函数容后再禀,先看一下返回值,把N=16带进去,就是:
    ((int32_t)x[2] << 15) + (x[1] >> 1)
    就是x[2]*2^15 + x[1]/2。这里没有什么道理可讲,随机数嘛,这只是一种方案而已(lrand48()采用的方案)。

    next()函数

    公式推导与化简

            next()是为redisLrand48()服务的static函数,也就是说对外不可见的,但是next()函数才是伪随机数生成算法的精髓所在。再回顾一遍线性同余公式:
    Xn+1 = (aXn + c) mod m, where n >= 0,m = 2^48
            注意:n和n+1都是X的下标。从数学角度来看很简单啊,先乘再加,最后取模。但是计算机做起来却不尽然,因为会溢出,所以我们是用数组存储的x和a。所以要做的是用数组模拟两个数的乘法运算。先把方程中的X和a表示出来:


    对线性同余方程进行一下换算:
    Xn+1 = (aXn + c) mod m
    Xn+1 = ((aXn) mod m + c mod m) mod m
    Xn+1 = ((aXn) mod m + c) mod m
            先计算一下a*Xn:

            这个多项式共有9个部分组成。再计算一下(a*Xn) mod m。因为m = 2^48,所以上述多项式中,2的幂次大于等于48的项一定是2^48的倍数,取模之后就是0,故可去掉这些项。所以(a*Xn)mod m的结果为:

            只剩下6项了。接着合并同类项,并加上c,很容易写出 a*Xn + c的结果:

            上述算式的每个括号中的内容就是在一次随机数生成之后x[2]、x[1]、x[0] 里面保存的新的内容(即用来表示Xn+1)。当然了编程去计算的时候还要考虑进位的问题。先看一个宏定义:

    用到的宏

    #define MUL(x, y, z)	{ int32_t l = (long)(x) * (long)(y); \
    		(z)[0] = LOW(l); (z)[1] = HIGH(l); }
    #define CARRY(x, y)	((int32_t)(x) + (long)(y) > MASK)
    #define ADDEQU(x, y, z)	(z = CARRY(x, (y)), x = LOW(x + (y)))
            很明显宏函数MUL(x,y,z)表示的是乘法运算,x和y相乘,结果用z来存储。z[0]存储低16位,z[1]存储高16位。
            CARRY(x,y)就是判断两个数相加是否会“进位”,这里的“进位”指的超出2个字节(16位)的大小。因为我们无论是数组a还是数组x,其中每个元素保存的都是2个字节的有效数据。也就是说,如果x[0]里面的数字超过2个字节,就要把多出的部分“进位”到x[1]中。每个元素其实都是4个字节的大小,之所以没有用到全部的4字节来存储,是因为当4字节全部用来存储数据时,相加以后可能就会溢出,编译器会弹出警告,其结果也会变成负数。
            ADDEQU(x,y,z)执行的操作是:x和y相加,其结果存储到x中。z中保存是否“进位”。

    next()源码

    static void next(void) {
        uint32_t p[2], q[2], r[2], carry0, carry1;
    
        MUL(a[0], x[0], p);
        ADDEQU(p[0], c, carry0);
        ADDEQU(p[1], carry0, carry1);
        MUL(a[0], x[1], q);
        ADDEQU(p[1], q[0], carry0);
        MUL(a[1], x[0], r);
        x[2] = LOW(carry0 + carry1 + CARRY(p[1], r[0]) + q[1] + r[1] +
                a[0] * x[2] + a[1] * x[1] + a[2] * x[0]);
        x[1] = LOW(p[1] + r[0]);
        x[0] = LOW(p[0]);
    }
            我们来一行一行的分析一下。声明语句不看,从第4行开始读。
        MUL(a[0], x[0], p);
        ADDEQU(p[0], c, carry0);
        ADDEQU(p[1], carry0, carry1);

    • MUL运算:a[0]和x[0]相乘,结果保存到数组p中。
    • 第一个ADDEQU:然后p[0]再和c相加,carry0标识是否有“进位”。这里完成的就是运算。
    • 第二个ADDEQU之后就是把低16位加上c之后是否进位,加到p[1],并且判断这次相加之后有没有产生新的进位(指2^16次多项式向2^32次多项式的进位)并保存到carry1。

    至此一次多项式相关的运算计数完毕,接下来是2^16次多项式的运算。


        MUL(a[0], x[1], q);
        ADDEQU(p[1], q[0], carry0);
        MUL(a[1], x[0], r);
    • 第一个MUL运算:a[0]和x[1]相乘,结果保存到数组q中。
    • ADDEQU运算:将p[1](存储了“低16位”运算之后向“中16位”进位的值)和q[0]相加,结果保存到p[1],carry0标识“中16位”(2^16次多项式)对高16位(2^32次多项式)是否有新的进位。
    • 第二个MUL运算:a[1]和x[0]相乘,结果保存到数组r中。
    至此完成了 系数相关运算。

        x[2] = LOW(carry0 + carry1 + CARRY(p[1], r[0]) + q[1] + r[1] +
                a[0] * x[2] + a[1] * x[1] + a[2] * x[0]);
        x[1] = LOW(p[1] + r[0]);
        x[0] = LOW(p[0]);
            倒着读吧,先看x[0],它保存的应该是一次多项式的结果。
            x[1]存储2^16次多项式的系数。p[1]里面存储着a[0]x[1]的结果以及低16位的进位。r[0]存储着a[1]x[0]的结果(不包括进位)。
            x[2]最复杂。回顾一下2^32次多项式的系数: 再看一眼,那行代码,这几个两两直接相乘的部分读懂了吧,那么可以去掉他们再看其他部分:
    carry0 + carry1 +CARRY(p[1], r[0]) + q[1] + r[1]
    剩余的多项式就是2^16次多项式在运算过程中向上的进位了。

            画了一个图给大家表示一下:
     
            这个图的上面两行是表头,下面彩色部分是所存储的内容。比如第三列表示x[0]里面存储的是p[0]和c的和。
            从第一幅图到第二幅图的转变是因为执行了  ADDEQU (p[ 1 ], q[ 0 ], carry0);这条语句,将q[0]加到了p[1]上。然后再去看看x[2]的那段代码,就清楚多了吧,重点是考虑进位。


    展开全文
  • 随机数的生成算法比较,包括一些代码,效率比较,以便实现蒙特卡罗法
  • 今天主要是来研究梅森旋转算法,...机数,并且效率高效,弥补了传统伪随机数生成器的不足。梅森旋转算法的最长周期取自一个梅森素数, 由此命名为梅森旋转算法。常见的两种为基于32位的MT19937-32和基于64位的MT19...

    今天主要是来研究梅森旋转算法,它是用来产生伪随机数的,实际上产生伪随机数的方法有很多种,比如线性同余法,

    平方取中法等等。但是这些方法产生的随机数质量往往不是很高,而今天介绍的梅森旋转算法可以产生高质量的伪随

    机数,并且效率高效,弥补了传统伪随机数生成器的不足。梅森旋转算法的最长周期取自一个梅森素数

    由此命名为梅森旋转算法。常见的两种为基于32位的MT19937-32和基于64位的MT19937-64

    由于梅森旋转算法是利用线性反馈移位寄存器(LFSR)产生随机数的,所以我们先来认识线性反馈移位寄存器

    首先,移位寄存器包括两个部分

        (1)级,每一级包含一个比特,比如11010110是一个8级的移位寄存器产生的

        (2)反馈函数,线性反馈移位寄存器的反馈函数是线性的,非线性反馈移位寄存器的反馈函数是非线性的

    一个级的移位寄存器产生的序列的最大周期为,当然这个最大周期跟反馈函数有很大关系,线性反馈函数实

    际上就是这个级的移位寄存器选取“某些位”进行异或后得到的结果,这里的“某些位”的选取很重要,得到线性反馈

    函数之后,把这个移位寄存器的每次向右移动一位,把最右端的作为输出,把“某些位”的异或结果作为输入放到最左

    端的那位,这样所有的输出对应一个序列,这个序列叫做M序列,是最长线性移位寄存器序列的简称。

    上面“某些位”的选取问题还没有解决,那么应该选取哪些位来进行异或才能保证最长周期为,这是一个很重要

    的问题。选取的“某些位”构成的序列叫做抽头序列,理论表明,要使LFSR得到最长的周期,这个抽头序列构成的多项

    式加1必须是一个本原多项式,也就是说这个多项式不可约,比如

    下面以一个4位的线性反馈移位寄存器为例说明它的工作原理。

     

    如果的值分别是1 0 0 0,反馈函数选取,那么得到如下序列

        

    可以看出周长为15。在这一个周期里面涵盖了开区间内的所有整数,并且都是没有固定顺序出现的,有

    很好的随机性。

    之前说过,梅森旋转算法的周期为,那么说明它是一个19937级的线性反馈移位寄存器,实际上基于32

    MT19937-32只需要用到32位,那么为什么要选择周长为的算法呢? 那是因为这样做随机性很好。

    梅森旋转算法是基于线性反馈移位寄存器的一直进行移位旋转,周期为一个梅森素数,果然是名副其实。

    梅森旋转算法Mersenne twister)是一个伪随机数发生算法。由松本真西村拓士[1]在1997年开发,基于有限二进制字段上的矩阵线性递归F_{2}。可以快速产生高质量的伪随机数, 修正了古典随机数发生算法的很多缺陷。

    梅森旋转算法是R,Python,Ruby,IDL,Free Pascal,PHP,Maple,Matlab,GMP和GSL的默认伪随机数产生器。从C++11开始,C++也可以使用这种算法。在Boost C++,Glib和NAG数值库中,作为插件提供。 在SPSS中,梅森选旋转算法是两个PRNG中的一个:另一个是产生器仅仅为保证旧程序的兼容性,梅森旋转被描述为”更加可靠“。梅森旋转在SAS中同样是PRNG中的一个,另一个产生器是旧时的且已经被弃用。

    最为广泛使用Mersenne Twister的一种变体是MT19937,可以产生32位整数序列。具有以下的优点:

    1. 有219937 − 1的非常长的周期。在许多软件包中的短周期—232 随机数产生器在一个长周期中不能保证生成随机数的质量。[2
    2. 在1 ≤ k ≤ 623的维度之间都可以均等分布(参见定义).
    3. 除了在统计学意义上的不正确的随机数生成器以外, 在所有伪随机数生成器法中是最快的(当时)

    算法详细

    本算法基于标准(线性)旋转反馈移位寄存器(twisted generalised feedback shift register/TGFSR)产生随机数

    算法中用到的变量如下所示:
        ·w:长度(以bit为单位)
        ·n:递归长度
        ·m:周期参数,用作第三阶段的偏移量
        ·r:低位掩码/低位要提取的位数
        ·a:旋转矩阵的参数
        ·f:初始化梅森旋转链所需参数
        ·b,c:TGFSR的掩码
        ·s,t:TGFSR的位移量
        ·u,d,l:额外梅森旋转所需的掩码和位移量
    
    
    MT19937-32的参数列表如下:
        ·(w, n, m, r) = (32, 624, 397, 31)
        ·a = 9908B0DF(16)
        ·f = 1812433253
        ·(u, d) = (11, FFFFFFFF16)
        ·(s, b) = (7, 9D2C568016)
        ·(t, c) = (15, EFC6000016)
        ·l = 18
    
    MT19937-64的参数列表如下:
        ·(w, n, m, r) = (64, 312, 156, 31)
        ·a = B5026F5AA96619E9(16)
        ·f = 6364136223846793005
        ·(u, d) = (29, 555555555555555516)
        ·(s, b) = (17, 71D67FFFEDA6000016)
        ·(t, c) = (37, FFF7EEE00000000016)
        ·l = 43

    参考链接:

    https://github.com/xuwei-k/tinymt

    https://en.wikipedia.org/wiki/Mersenne_Twister#TinyMT

    http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/TINYMT/JAVA/index.html

    https://cs.gmu.edu/~sean/research/mersenne/MersenneTwister.java

    https://cs.gmu.edu/~sean/research/mersenne/MersenneTwisterFast.java

    展开全文
  • 伪随机数生成算法(1)线性同余法

    千次阅读 2014-04-29 09:05:22
    古老的LCG(linear congruential generator)代表了最好最朴素的伪随机数产生器算法。主要原因是容易理解,容易实现,而且速度快。  LCG 算法数学上基于公式: X(n+1) = (a * X(n) + c) % m 其中...
  • python实现-伪随机数生成
  • matlab——伪随机数生成

    千次阅读 2019-11-13 19:30:27
    rand(m) 用于生成m行m列均匀分布在(0,1)之间的伪随机数 实现 >> rand(5) ans = 0.8147 0.0975 0.1576 0.1419 0.6557 0.9058 0.2785 0.9706 0.4218 0.0357 0.1270 0.5469 0.9572 0....
  • 伪随机数产生程序

    2013-04-19 15:35:55
    产生伪随机数的一个C程序,可以修改产生范围。
  • 网址mark: https://www.zhihu.com/question/20222653不重复随机数列生成算法: http://www.cnblogs.com/eaglet/archive/2011/01/17/1937083.html
  • 二维联合正态分布伪随机数生成算法的研究与实现。。。。。。。。。。。
  • 每种算法将以多种语言实现。 首先,我熟悉Python和JavaScript,因此将首先实现它们。 其他语言。 什么 每个CSPRNG均以十进制或原始二进制形式打印随机数。 范围取决于密码原语。 通常为[0,2 ^ 128)或[0,2 ^ 160)...
  • 在工程中有时候需要用到随机数函数来模拟一些情况,例如加密系统的密钥来源可以用随机数函数获取。...根据以上三个性质,可以将随机数函数分为“弱伪随机数”,“强伪随机数”,“真随机数”。其中“真随机数”靠软...
  • 今天主要是来研究梅森旋转算法,它是...机数,并且效率高效,弥补了传统伪随机数生成器的不足。梅森旋转算法的最长周期取自一个梅森素数, 由此命名为梅森旋转算法。常见的两种为基于32位的MT19937-32和基于64位的MT...
  • 伪随机数算法

    2021-02-14 21:41:20
    伪随机数算法
  • C++伪随机数生成算法

    2012-07-29 08:47:35
    static long holdrand = 1L; void __cdecl srand (unsigned int seed) { holdrand = (long)seed; } int __cdecl rand (void) { return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7ff
  • 一个伪随机数生成算法

    千次阅读 2011-02-12 14:49:00
    一个伪随机数生成算法 这几天逛程序员论坛,发现了不少好帖子,增长了不少知识,现拿其中一则为例说明。 某人提出一个问题,说怎么样能生成一亿个不重复的随机数呢? 问题表述起来很简单,似乎...
  • Python——伪随机数生成

    千次阅读 2018-10-28 20:27:27
    伪随机数生成器,顾名思义就是它能产生随机数!,实际上这种生成器就是一个小算法,通过一定的算法去生成一个个的随机数。 现在网上流行的伪随机生成器的算法大致分为两种: 1.平方取中法 2.线性同余法 线性同...
  • 8位单片机产生伪随机数算法(6502版)[参考].pdf
  • 另见另一个博客点击打开链接
  • 伪随机数生成算法及性能检验

    万次阅读 2012-10-24 14:10:30
    什么叫伪随机数  在一些问题中,比如计算机仿真和模拟、密码学等应用中,需要产生一个随机数数列来解决问题。  随机数数列分为真随机数数列和伪随机数数列。真随机数数列是完全不可预测的,可以通过放射性衰变、...
  • 1 真随机数 真正意义上的随机数(或者随机事件)在某次产生过程...计算机只能生成相对的随机数,即伪随机数。 从定义我们可以了解到,伪随机数其实是有规律的。只不过这个规律周期比较长,但还是可以预测的。主要原因就
  • 伪随机数C语言编程

    千次阅读 2018-06-10 22:38:03
    本文介绍在 Linux 编程环境下,如何生成伪随机数。 什么是伪随机数 伪随机数是通过一个确定性的算法计算出来的“似乎”是随机的数序,因此伪随机数实际上并不随机。在计算伪随机数时,假如初始值不变的话,那么...
  • 伪随机数生成

    千次阅读 2018-10-13 11:48:03
    一 点睛 随机数可以通过硬件来生成,也可以通过软件来生成。 通过硬件生成的随机数列,是根据传感器收集的热量、声音的变化等事实上无法预测...伪随机数生成器具有“内部状态”,并根据外部输入的“种子”来生成...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 43,462
精华内容 17,384
关键字:

伪随机数生成算法

友情链接: TestAES.zip