纯线性同余随机数生成器

我不是女神ヾ 2022-08-05 11:12 22阅读 0赞

1.  线性同余随机数生成器介绍：

古老的LCG(linear congruential generator)代表了最好最朴素的伪随机数产生器算法。主要原因是容易理解，容易实现，而且速度快。

LCG 算法数学上基于公式：

X(n+1) = (a \* X(n) + c) % m

其中，各系数为：

模m, m > 0 
系数a, 0 < a < m 
增量c, 0 <= c < m 
原始值(种子) 0 <= X(0) < m 
其中参数c, m, a比较敏感，或者说直接影响了伪随机数产生的质量。 
一般而言，高LCG的m是2的指数次幂(一般2^32或者2^64)，因为这样取模操作截断最右的32或64位就可以了。多数编译器的库中使用了该理论实现其伪随机数发生器rand()。

下面是部分编译器使用的各个参数值：

<table style="border:1px solid silver; border-collapse:collapse; word-break:break-word"> 
 <tbody> 
 <tr> 
 <td style="font-size:14px; border:0.5pt solid; border-collapse:collapse; padding:3px 7px"> Source </td> 
 <td style="font-size:14px; border-top-width:0.5pt; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:solid solid solid none; border-collapse:collapse; padding:3px 7px"> m </td> 
 <td style="font-size:14px; border-top-width:0.5pt; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:solid solid solid none; border-collapse:collapse; padding:3px 7px"> a </td> 
 <td style="font-size:14px; border-top-width:0.5pt; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:solid solid solid none; border-collapse:collapse; padding:3px 7px"> c </td> 
 <td style="font-size:14px; border-top-width:0.5pt; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:solid solid solid none; border-collapse:collapse; padding:3px 7px"> rand() / Random(L)的种子位 </td> 
 </tr> 
 <tr> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-left-width:0.5pt; border-style:none solid solid; border-collapse:collapse; padding:3px 7px"> Numerical Recipes </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 2^32 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 1664525 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 1013904223 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> &nbsp;</td> 
 </tr> 
 <tr> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-left-width:0.5pt; border-style:none solid solid; border-collapse:collapse; padding:3px 7px"> Borland C/C++ </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 2^32 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 22695477 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 1 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 位30..16 in rand(), 30..0 in lrand() </td> 
 </tr> 
 <tr> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-left-width:0.5pt; border-style:none solid solid; border-collapse:collapse; padding:3px 7px"> glibc (used by GCC) </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 2^32 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 1103515245 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 12345 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 位30..0 </td> 
 </tr> 
 <tr> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-left-width:0.5pt; border-style:none solid solid; border-collapse:collapse; padding:3px 7px"> ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++ </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 2^32 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 1103515245 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 12345 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 位30..16 </td> 
 </tr> 
 <tr> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-left-width:0.5pt; border-style:none solid solid; border-collapse:collapse; padding:3px 7px"> Borland Delphi, Virtual Pascal </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 2^32 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 134775813 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 1 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 位63..32 of (seed * L) </td> 
 </tr> 
 <tr> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-left-width:0.5pt; border-style:none solid solid; border-collapse:collapse; padding:3px 7px"> Microsoft Visual/Quick C/C++ </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 2^32 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 214013 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 2531011 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 位30..16 </td> 
 </tr> 
 <tr> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-left-width:0.5pt; border-style:none solid solid; border-collapse:collapse; padding:3px 7px"> Apple CarbonLib </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 2^31-1 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 16807 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 0 </td> 
 <td style="font-size:14px; border-right-width:0.5pt; border-bottom-width:0.5pt; border-style:none solid solid none; border-collapse:collapse; padding:3px 7px"> 见Park–Miller随机数发生器 </td> 
 </tr> 
 </tbody> 
</table>

LCG不能用于随机数要求高的场合，例如不能用于Monte Carlo模拟，不能用于加密应用。  
LCG有一些严重的缺陷，例如如果LCG用做N维空间的点坐标，这些点最多位于m1/n超平面上(Marsaglia定理)，这是由于产生的相继X(n)值的关联所致。  
另外一个问题就是如果m设置为2的指数，产生的低位序列周期远远小于整体。  
一般而言，输出序列的基数b中最低n位，bk = m (k是某个整数)，最大周期bn.  
有些场合LCG有很好的应用，例如内存很紧张的嵌入式中，电子游戏控制台用的小整数，使用高位可以胜任。

（2） C语言中伪随机数生成方法：rand(),srand(time(null))的解析

C语言中伪随机数生成算法实际上是采用了"线性同余法"。具体的计算如下：

Xi = (Xi-1 \* A + C ) mod M

其中A,C,M都是常数（一般会取质数）。当C=0时，叫做乘同余法。引出一个概念叫seed，它会被作为X0被代入上式中，然后每次调用rand()函数都会用上一次产生的随机值来生成新的随机值。可以看出实际上用rand()函数生成的是一个递推的序列，一切值都来源于最初的 seed。所以当初始的seed取一样的时候，得到的序列都相同。

C语言里面有RAND\_MAX这样一个宏，定义了rand()所能得到的随机值的范围。在C里可以看到RAND\_MAX被定义成0x7fff，也就是32767。rand()函数里递推式中M的值就是32767。

线性同余法生成的是伪随机数，粗略符合均匀分布。根据中心极限定理，任何分布的噪声，通过反复相加，就可以成为高斯噪声。

**函数原型**

1、C++标准函数库提供一随机数生成器rand，返回0－RAND\_MAX之间均匀分布的伪随机整数。 RAND\_MAX必须至少为32767。rand()函数不接受参数，默认以1为种子（即起始值）。随机数生成器总是以相同的种子开始，所以形成的伪随机数列也相同，失去了随机意义。（但这样便于程序调试）

2、C++中另一函数srand（），可以指定不同的数（无符号整数变元）为种子。但是如果种子相同，伪随机数列也相同。一个办法是让用户输入种子，但是仍然不理想。

3、 比较理想的是用变化的数，比如时间来作为随机数生成器的种子。time的值每时每刻都不同。所以种子不同，所以，产生的随机数也不同。

// C++随机函数（VC program）

\#include <stdio.h>

\#include <iostream>

\#include <time.h>

using namespace std;

\#define MAX 100