线性同余法生成伪随机数

线性同余法

选择四个数:模数$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$个数,然后开始重复。