每日总结-第二十五天-梅森旋转算法

参考链接

https://blog.csdn.net/tick_tock97/article/details/78657851

算法结构

整个算法分为三个阶段（如图所示）：
第一阶段：初始化，获得基础的梅森旋转链；
第二阶段：对于旋转链进行旋转算法；
第三阶段：对于旋转算法所得的结果进行处理；

常量

算法中用到的变量如下所示：
    ·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

伪代码

#include <stdint.h>

// 定义MT19937-32的常数
enum
{
    // 假定 W = 32 (此项省略)
    N = 624,
    M = 397,
    R = 31,
    A = 0x9908B0DF,

    F = 1812433253,

    U = 11,
    // 假定 D = 0xFFFFFFFF (此项省略)

    S = 7,
    B = 0x9D2C5680,

    T = 15,
    C = 0xEFC60000,

    L = 18,

    MASK_LOWER = (1ull << R) - 1,
    MASK_UPPER = (1ull << R)
};

static uint32_t  mt[N];
static uint16_t  index;

// 根据给定的seed初始化旋转链
void Initialize(const uint32_t  seed)
{
    uint32_t  i;
    mt[0] = seed;
    for ( i = 1; i < N; i++ )
    {
        mt[i] = (F * (mt[i - 1] ^ (mt[i - 1] >> 30)) + i);
    }
    index = N;
}

static void Twist()
{
    uint32_t  i, x, xA;
    for ( i = 0; i < N; i++ )
    {
        x = (mt[i] & MASK_UPPER) + (mt[(i + 1) % N] & MASK_LOWER);
        xA = x >> 1;
        if ( x & 0x1 )
        {
            xA ^= A;
        }
        mt[i] = mt[(i + M) % N] ^ xA;
    }

    index = 0;
}

// 产生一个32位随机数
uint32_t ExtractU32()
{
    uint32_t  y;
    int       i = index;
    if ( index >= N )
    {
        Twist();
        i = index;
    }
    y = mt[i];
    index = i + 1;
    y ^= (y >> U);
    y ^= (y << S) & B;
    y ^= (y << T) & C;
    y ^= (y >> L);
    return y;
}

使用boost生成随机数

// uniform_smallint：在小整数域内的均匀分布  
// uniform_int：在整数域上的均匀分布  
// uniform_01：在区间[0,1]上的实数连续均匀分布  
// uniform_real：在区间[min,max]上的实数连续均匀分布  
// bernoulli_distribution：伯努利分布  
// binomial_distribution：二项分布  
// cauchy_distribution：柯西（洛伦兹）分布  
// gamma_distribution：伽马分布  
// poisson_distribution：泊松分布  
// geometric_distribution：几何分布  
// triangle_distribution：三角分布  
// exponential_distribution：指数分布  
// normal_distribution：正态分布  
// lognormal_distribution：对数正态分布  
// uniform_on_sphere：球面均匀分布  
void test_random_distribute()  
{  
    boost::mt19937 rng(time(0));  //以时间为种子创建一个伪随机数发生器
// 1. uniform_int  
    boost::uniform_int<> ui(0, 255);  
    for (int i = 0; i < 10; ++i)  
    {   
        std::cout<< ui(rng) << std::endl;  
    }  
// 2. uniform_01  
    boost::uniform_01<boost::mt19937&> u01(rng);  
    for (int i = 0; i < 10; ++i)  
    {   
        std::cout<< u01() << std::endl;  
    }  
}