线性同余法详解

发布时间：2023-05-20

一、基础概念

线性同余法（Linear congruential generator，简称LCG）是一种伪随机数生成器。其具体思想是以一种线性的方式对一个起始值进行递推计算，以得到一个序列化的伪随机数序列。LCG可以形式化地表示为：Xn+1 = (aXn + c) mod m，其中Xn+1是下一个伪随机数，Xn是当前伪随机数，a、c、m是先验设定好的参数，mod表示模运算。 LCG能够快速地生成大量的伪随机数，因此被广泛地应用于模拟、密码学等领域，同时也是许多编程语言中的随机数生成器的核心算法。

二、算法细节

在LCG中，参数a、c和m需要精心设计，否则可能导致随机数生成效果不佳。以下是一些需要注意的细节：

1.参数m

参数m应该为一个较大的质数，以确保随机数循环周期的长度较长，保证生成的伪随机数足够分散。同时，m也需要足够小，否则会影响算法执行的效率。

const int m = 2147483647; // 2^31 - 1

2.参数a

参数a需要满足以下条件： 1）a和m互质，以保证伪随机数的分散性。 2）a-1能够被m的所有质因子整除，以避免伪随机数循环周期过短。

const int a = 16807; // 随意选取的常数

3.参数c

参数c一般取0或1，不会对伪随机数的质量产生影响。如果使用C++标准库中的rand函数，其使用的是a=1103515245, c=12345, m=2147483647的LCG。

const int c = 0; // 常数c一般取0或1

三、优化方法

LCG是一种简单但不一定高效的伪随机数生成器，其生成的伪随机数分布不够均匀，容易被攻击者破解。为了弥补LCG的不足，可以采取以下优化方法：

1.超前迭代法

超前迭代法是一种通过多次递归来产生更高质量随机数的方法，它可以显著提高LCG的效率和随机性。在超前迭代法中，可以使用两个LCG，其中一个作为“控制器”，控制另一个的参数。这种方法可以产生出高质量的随机数序列，但需要占用相当大的空间。

// 线性同余法优化：超前迭代法
class Random {
public:
    Random() {
        // 控制器LCG
        c_r = c0_r;
        a_r = a0_r;
        m_r = m0_r;
        x_r = time(nullptr);
        for (int i = 0; i < 10; i++) {
            next_r();
        }
    }
    int next_r() {
        int x = x_r;
        // LCG1作为控制器
        x_r = (a0_r * x_r + c0_r) % m0_r;
        // LCG2作为普通LGC
        return (a_r * x + c_r) % m_r;
    }
private:
    const int c0_r = 1;
    const int a0_r = 16807;
    const int m0_r = 2147483647;
    int c_r, a_r, m_r, x_r;
};

2.多项式同余法

多项式同余法是一种比LCG更高效的伪随机数生成算法。它使用多项式函数来代替线性函数，进一步提升了随机数生成效率和质量。不过，这种方法需要较大的空间，在实际应用时需要权衡空间和时间的开销。

// 多项式同余法
class Random {
public:
    Random() {
        for (int i = 0; i < degree_r; i++) {
            a_r[i] = rand();
        }
    }
    int next_r() {
        int x = a_r[0];
        for (int i = 1; i < degree_r; i++) {
            x = (a_r[i] + x * seed_r) % m_r;
        }
        for (int i = 0; i < degree_r-1; i++) {
            a_r[i] = a_r[i+1];
        }
        a_r[degree_r-1] = x;
        return x;
    }
private:
    const int m_r = 2147483647;
    const int seed_r = 212885;
    const int degree_r = 10;
    int a_r[degree_r];
};

四、应用实例

以下是一个应用LCG生成模拟数据的实例。在这个例子中，使用LCG和超前迭代法的组合产生了10000个随机数，用于绘制一个符合正态分布的数据图表。

#include <iostream>
#include <vector>
#include <cmath>
#include <fstream>
#include <string>
#include <ctime>
class Random {
public:
    Random() {
        c_r = c0_r;
        a_r = a0_r;
        m_r = m0_r;
        x_r = time(nullptr);
        for (int i = 0; i < 10; i++) {
            next_r();
        }
    }
    int next_r() {
        int x = x_r;
        x_r = (a0_r * x_r + c0_r) % m0_r;
        return (a_r * x + c_r) % m_r;
    }
private:
    const int c0_r = 1;
    const int a0_r = 16807;
    const int m0_r = 2147483647;
    int c_r, a_r, m_r, x_r;
};
int main() {
    Random random;
    std::vector<double> nums;
    for (int i = 0; i < 10000; i++) {
        nums.push_back(random.next_r() / static_cast<double>(random.m0_r));
    }
    // 使用Box-Muller变换将均匀分布转换为正态分布
    std::vector<double> nums2;
    for (int i = 0; i < 10000; i += 2) {
        double u1 = nums[i];
        double u2 = nums[i + 1];
        double z1 = sqrt(-2 * log(u1)) * cos(2 * M_PI * u2);
        double z2 = sqrt(-2 * log(u1)) * sin(2 * M_PI * u2);
        nums2.push_back(z1);
        nums2.push_back(z2);
    }
    // 统计数据
    double sum = 0, avg = 0, stdev = 0;
    for (auto num : nums2) {
        sum += num;
    }
    avg = sum / nums2.size();
    for (auto num : nums2) {
        stdev += pow(num - avg, 2);
    }
    stdev = sqrt(stdev / (nums2.size() - 1));
    // 输出结果到文件
    std::ofstream out("output.txt");
    for (auto num : nums2) {
        out << num << std::endl;
    }
    out.close();
    std::cout << "avg = " << avg << std::endl;
    std::cout << "stdev = " << stdev << std::endl;
    return 0;
}
推荐文章