线性同余发生器学习笔记

· · 科技·工程

前言

大家好，今天我忘记了 mt_19937、rand 等函数和 C++ 的使用方法，但我想使用随机化，于是我学会了线性同余发生器。

这真是我写过内容最浅显的文章了，我自己都觉得丢人。

介绍

线性同余发生器是一种简单的随机数生成算法，如果 X_i 是它生成出的第 i 个随机数，则有：

X_i=\begin{cases} \text{seed} & i=1 \\ (kX_{i-1}+b)\operatorname{mod}m & \text{Otherwise} \end{cases}

显然这是一个递推公式，其中 k, b, m, \text{seed} 是我们选定的一些正整数且 k, b, \text{seed}\lt m。

然后我们来研究线性同余发生器生成的随机数有什么性质。

首先根据这个递推式，我们可以发现如果 X_i=X_j，则 X_{i+1}=X_{j+1}，也就是说线性同余发生器生成出的随机数是有周期性的，而且看起来周期并不长。

然后我们又可以观察到周期的上限是 m，因为在理想状态下，一个周期中的数最多有 m 个且当 k=1, b=1 时可以把所有数都取到，所以这就是上限了。

但很多时候周期的长度取不到上限 m，所以线性同余发生器是无法生成 \mathbb{Z}\cap[0, m-1] 中的所有数的。

所以我们要研究怎样选取 k, b, m, \text{seed} 使得生成的随机数尽可能均匀。

我们可以先尝试一个例子，其中 \text{seed}=1, k=1145141, b=0, m=2^{32}-1：

(define (next x k b m)
  (remainder (+ (* k x) b) m))

(define rand
  (let ((x 1)
        (k 1145141)
        (b 0)
        (m 4294967295))
    (lambda ()
      (set! x (next x k b m))
      x)))

（我依然没有想起怎么用 C++）

（如果你不知道 Scheme 是什么以及怎么使用，可以去阅读《计算机程序的构造与解释》）

这个随机数生成器看起来随机性还不赖，我们可以通过蒙特卡罗法来检验一下：

(define (monte n)
  (define (rnd)
    (/ (rand) 4294967295.0))
  (let it ((res n)
           (d 0))
    (if (= res 0)
        (/ (* 4.0 d) n)
        (it (- res 1)
            (+ d
               (let ((x (rnd))
                     (y (rnd)))
                 (if (<= (+ (* x x) (* y y)) 1) 1 0)))))))

然后 load 之后用 (monte 114514) 启动，第一次计算的结果是 3.145117627538991。[^1]

[^1]: 在我想起 C++ 的 rand 的参数后，我尝试以 1 为随机种子，结果是 3.137712419442164。

于是我们得出了结论：m 只要很大就行，\text{seed} 取一个随机数就行（比如时间戳），k, b 按自己的喜好选两个质数就可以。

好吧，其实我也不知道，网上也没有找到什么这方面的资料，但这里有一些其他例子：^2

名称 k b m
RANDU 65539 0 2^{31}
MINSTD 16807 0 2^{31}-1
Numerical Recipes 65539 1013904223 2^{32}
glibc rand() 1103515245 12345 2^{31}
MSVC++ 214013 2531011 2^{32}

参考文献（不撒花了）

线性同余发生器_百度百科

算法：线性同余法(LCG,Linear Congruential Generator)-CSDN博客

线性同余发生器与伪随机数 - Qcer - 博客园

随机函数 - OI Wiki