线性同余发生器

线性同余发生器

线性同余发生器(Linear congruential generator,LCG)是一种能产生具有不连续计算的伪随机序列的分段线性方程的算法,它代表了最古老和最知名的伪随机序列生成器算法之一。

生成器定义

$$
X_{n+1}=\left(a X_{n}+c\right) \bmod m
$$

  • $X​$是伪随机序列

  • $m,m>0​$表示模量

  • $a,0<a<m​$表示乘数

  • $c,\leq0<m​$表示增量

  • $ X_{0},0\leq X_{0}<m $表示初始值

当$c=0$时,该发生器称为乘法同余发生器MCG

MCG的实现

#include <stdio.h>

#define A 48271L
#define M 2147483647L

double Random(void) {
    Seed = (A * Seed) % M;
    return (double)Seed / M;
}
void Initialize(unsigned InitVal) {
    Seed = InitVal;
}

这种实现方法实现地很直观,但存在一个问题。在32位机器上A * Seed会导致乘法溢出与截断,虽然程序能继续运行,但它影响最终的计算结果,从而影响伪随机性。

Schrage's method

Schrage方法推导过程
推导过程
因为$R<Q$,故所有的余项均可计算而没有溢出。此外,仅当余项的值小于0时候$\delta\left(x_{i}\right)=1$。

#include <stdio.h>

#define A 48271L
#define M 2147483647L
#define Q ( M / A )
#define R ( M % A )

static unsigned long Seed = 1;

double Random(void) {
    long TmpSeed;
    TmpSeed = A * (Seed % Q) - R * (Seed / Q);
    if (TmpSeed >= 0)
    {
        Seed = TmpSeed;
    }
    else
    {
        Seed = TmpSeed + M;
    }
    return (double)Seed / M;
}
void Initialize(unsigned InitVal) {
    Seed = InitVal;
}

标签: none

评论已关闭