线性同余法生成伪随机数

线性同余法

选择四个数: 模数 $m$、乘数 $a$、增量 $c$、和种子 $x_0$,使得 $2\le a\lt m$,$0\le c\lt m$,$0\le x_0 m$。生成伪随机序列 ${x_n}$,使得对所有 $n$,$0\le x_n \lt m$。生成的办法是逐次同余:$$x_{n+1} = (ax_n +c)\;\mathbf {mod}\; m$$。

示例

例如,选取 $m=9,a=7,c=4,x_0=3$,产生的伪随机数序列如下:
$$
x_1 = 7x_0+4\;\mathbf {mod}\; 9 = 25\;\mathbf {mod}\; 9=7\\
x_2 = 7x_1+4\;\mathbf {mod}\; 9 = 53\;\mathbf {mod}\; 9=8\\

$$
常使用的线性同余发生器的增量 $c=0$。这样的发生器称为 纯乘式发生器。例如以 $2^{31}-1$ 为模,以 $7^5$ 为乘数的纯乘式发生器就广为采用。会产生 $2^{31}-2$ 个数,然后开始重复。