线性反馈移位寄存器与梅森旋转算法

本是古典何须时尚 2022-03-28 08:13 131阅读 0赞

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

平方取中法等等。可是这些方法产生的随机数质量往往不是非常高，而今天介绍的**梅森旋转算法**能够产生高质量的伪随

机数，而且效率高效，弥补了传统伪随机数生成器的不足。**梅森旋转算法**的最长周期取自一个梅森素数![20140611143844281][]，由

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

因为**梅森旋转算法**是利用**线性反馈移位寄存器（LFSR）**产生随机数的，所以我们先来认识**线性反馈移位寄存器**。

首先，移位寄存器包含两个部分

（1）级，每一级包括一个比特，比方**11010110**是一个**8**级的移位寄存器产生的

（2）反馈函数，线性反馈移位寄存器的反馈函数是线性的，非线性反馈移位寄存器的反馈函数是非线性的

一个![20140611133317359][]级的移位寄存器产生的序列的最大周期为![20140611133422859][]，当然这个最大周期跟反馈函数有非常大关系，线性反馈函数实

际上就是这个![20140611133317359][]级的移位寄存器选取“某些位”进行异或后得到的结果，这里的“某些位”的选取非常重要，得到线性反

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

左端的那位，这样全部的输出相应一个序列，这个序列叫做**M序列**，是**最长线性移位寄存器序列**的简称。

上面“某些位”的选取问题还没有解决，那么应该选取哪些位来进行异或才干保证最长周期为![20140611133422859][]，这是一个非常重要

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

项式加**1**必须是一个**本原多项式**，也就是说这个多项式不可约，比方![20140611135052328][]。

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

![20140611141904468][]

假设![20140611142030953][]的值各自是**1 0 0 0**，反馈函数选取![20140611135052328][]，那么得到例如以下序列

![20140611142718078][]

![20140611142831937][]

能够看出周长为**15**。在这一个周期里面涵盖了开区间![20140611144947593][]内的全部整数，而且都是没有固定顺序出现的，有非常好

的随机性。

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

的**MT19937-32**仅仅须要用到**32**位，那么为什么要选择周长为![20140611145309406][]的算法呢？ 那是由于这样做随机性非常好。

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

**代码：**

#include <iostream>
    #include <string.h>
    #include <stdio.h>
    #include <time.h>
    
    using namespace std;
    
    bool isInit;
    int index;
    int MT[624];  //624 * 32 - 31 = 19937
    
    void srand(int seed)
    {
        index = 0;
        isInit = 1;
        MT[0] = seed;
        for(int i=1; i<624; i++)
        {
            int t = 1812433253 * (MT[i-1] ^ (MT[i-1] >> 30)) + i;
            MT[i] = t & 0xffffffff;   //取最后的32位
        }
    }
    
    void generate()
    {
        for(int i=0; i<624; i++)
        {
            // 2^31 = 0x80000000
            // 2^31-1 = 0x7fffffff
            int y = (MT[i] & 0x80000000) + (MT[(i+1) % 624] & 0x7fffffff);
            MT[i] = MT[(i + 397) % 624] ^ (y >> 1);
            if (y & 1)
                MT[i] ^= 2567483615;
        }
    }
    
    int rand()
    {
        if(!isInit)
            srand((int)time(NULL));
        if(index == 0)
            generate();
        int y = MT[index];
        y = y ^ (y >> 11);
        y = y ^ ((y << 7) & 2636928640);
        y = y ^ ((y << 15) & 4022730752);
        y = y ^ (y >> 18);
        index = (index + 1) % 624;
        return y;
    }
    
    int main()
    {
        srand(0);  //设置随机种子
        int cnt = 0;
        for(int i=0; i<1000000; i++)
        {
            if(rand() & 1)
                cnt++;
        }
        cout<<cnt / 10000.0<<"%"<<endl;
        return 0;
    }

实际上在非常多语言中的随机数函数都已经採用了梅森旋转法实现，比方**Python**中的随机数模块**random**就是採用了梅

森旋转算法来产生伪随机数列，**C++11**中也有梅森旋转算法实现的随机数生成器。

**梅森旋转算法在信息指纹技术中的应用**

在**百度**或者**Google**这种搜索引擎中，爬虫要对爬取的网页进行判重，这个是通过信息指纹来实现的。详细来说就

是把每个网址随机地映射到**128**位二进制，这样每个网址仅仅占用**16**个字节的空间，这个**128**位的随机数就是这个

网址的信息指纹，能够证明，仅仅要产生的随机数足够好，那么就能够保证差点儿不可能有两个网址的信息指纹同样，就

如同不可能有两个人的指纹同样一样，而梅森旋转算法是产生高质量伪随机数的算法。

[20140611143844281]: /images/20220328/aba3e048d2b24dcaa6123463d2854be9.png
[20140611133317359]: /images/20220328/cb6b6d6118194ec88a94cabf44545c63.png
[20140611133422859]: /images/20220328/aa81104d8f8e4b7b9d59ae8c2f861f6c.png
[20140611135052328]: /images/20220328/043322a720b64ae7afeb91106797f7e1.png
[20140611141904468]: /images/20220328/00594c85aa04423bbc4e2a16794cf652.png
[20140611142030953]: https://img-blog.csdn.net/20140611142030953
[20140611142718078]: /images/20220328/6244b2769f574d01bd522f2c91ccf42f.png
[20140611142831937]: /images/20220328/79f4b87182b74846a9fed0a90c5f968c.png
[20140611144947593]: /images/20220328/e436b5b4feda4143b1ff79da4f52484f.png
[20140611145309406]: /images/20220328/c4f611f9e2b44fb8963e397ad95af655.png