C语言实现梅森旋转算法

原理: 梅森旋转算法是一种伪随机数生成算法

1.定义相关宏和结构体

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef unsigned int uint;

#define MT_199332_N 624
#define MT_199332_F 1812433253U
#define MT_199332_W 32
#define MT_199332_R 31
#define MT_199332_M 397
#define MT_199332_A 0x9908B0DF
#define MT_199332_U 11
#define MT_199332_D 0xffffffff
#define MT_199332_S 7
#define MT_199332_B 0x9d2c5680
#define MT_199332_T 15
#define MT_199332_C 0xefc60000
#define MT_199332_L 18
#define MT_199332_LOWER_MASK ((1U<<MT_199332_R)-1)
#define MT_199332_UPPER_MASK (1U<<MT_199332_R)

2.随机数种子函数

uint mt_seed(uint seed, uint *mt, int n)
{
    int i;

    memset(mt, 0x00, n*sizeof(uint));

    for(i=1; i<n; i++)
    {
        mt[i] = MT_199332_F * (mt[i-1]^mt[i-1]>>(MT_199332_W-2))+i;
    }

    return mt[n-1];
}

3.函数实现

uint mt_twist(uint *mt, int n)
{
    uint x, y;
    int i;

    for(i=0; i<n; i++)
    {
        x = (uint)((mt[i] & MT_199332_UPPER_MASK) + (mt[(i+1)%n] & MT_199332_LOWER_MASK));
        y = (x >> 1);

        if((x & 1) != 0)
        {
            y = (y ^ MT_199332_A);
        }

        mt[i] = (mt[(i+MT_199332_M)%n] ^ y);
    }

    return 0;
}

uint mt_extract(uint *mt, int n, uint *index)
{
    uint x;

    if(*index >= n)
    {
        mt_twist(mt, n);
    }

    x = x ^ x >> MT_199332_U & MT_199332_D;
    x = x ^ x << MT_199332_S & MT_199332_B;
    x = x ^ x << MT_199332_T & MT_199332_C;
    x = x ^ x >> MT_199332_L;

    (*index)++;

    return x;
}

4.主函数部分

int main()
{
    uint mt[MT_199332_N];
    uint index = 0;
    int n = MT_199332_N;

    mt_seed(time(NULL), mt, n);

    printf("random=[0x%08lx]\n", mt_extract(mt, n, &index));
    printf("random=[0x%08lx]\n", mt_extract(mt, n, &index));

    return 0;
}

5.编译

$ gcc -o example examle.c

6.运行

$ ./example

7.运行结果

random=[0x589cbc20]
random=[0xafc17fe5]