用线性同余法生成伪随机数

太过爱你忘了你带给我的痛 2023-10-08 10:58 15阅读 0赞

### 用线性同余法生成伪随机数 ###

在计算机上可以用物理方法来产生随机数，但价格昂贵，不能重复，使用不便。另一种方法是用数学递推公式产生，这样产生的序列与真正的随机数序列不同，所以称为伪随机数或伪随机序列，只要方法和参数选择合适，所产生的伪随机数就能满足均匀性和独立性，与真正的随机数具有相近的性质。

产生随机数的方法是先用一定的方法产生\[0,1\]均匀分布的随机数，然后通过一个适当的变换就可以得到符合某一概率模型的随机数。

**原理**：假设我们要生成伪随机数列为R0、R1、R2…。首先，我们根据伪随机数的种子，用下列公式计算第一个伪随机数R0  
**R0=（A\*种子+C）mod M**  
接下来用R0生成R1，R1生成R2，递归即可

当a=0时为和同余法，当c=0时为乘同余法，c≠0时为混合同余法

常用的产生\[0,1\]均匀分布的随机数的方法有乘同余法和混合同余法。

简而言之，线性同余法就是将当前的伪随机数值乘以A再加上C,然后将除以M得到的余数作为下一个伪随机数。在线性同余法中，最近一次生成的伪随机数的值就是内部状态，伪随机数的种子被用来对内部状态进行初始化。

在线性同余法中，只要谨慎选择A、C、M的值，就能够很容易地生成具备随机性的伪随机数列。

由于伪随机数是除以M得到的余数，因此其范围必定是0~M-1，而且生成的随机数会呈现一定周期（打个比方，x mod 12 代表的是钟表刻度，它的值永远在0-11之间,这个概念在数学里叫”同余”）。而且根据A、C、M的值，最终只能生成上述范围中的一部分值（因此周期会缩短）。

线性同余法的最大周期是m，但一般情况下会小于m。要使周期达到最大，应该满足以下条件：  
(1) c和m互质；  
(2) m的所有质因子的积能整除a-1；  
(3) 若m是4的倍数，则a-1也是；  
(4) a，c，r0（初值，一般即种子）都比m小；  
(5) a，c是正整数。

线性同余方法速度快，如果对乘数和模数进行适当的选择，可以满足用于评价一个随机数产生器的3 种准则：  
(1)这个函数应该是一个完整周期的产生函数。也就是说，这个函数应该在重复之前产生出0 到m之间的所有数；  
(2)产生的序列应该看起来是随机的；  
(3)这个函数应该用32bit 算术高效实现。

使用混合同余法  
Ri+1=(a\*Ri+c)mod(m)  
Yi+1=Ri+1/m  
在matlab中自己选取a,c,m与其内置函数rand比较：

function A = fakerand( a,c,m,r0 )
    A=zeros(100,1);
    R=zeros(100,1);
    R(1)=mod((a*r0+c),m);
    A(1)=R(1)/m;
    for i=1:99
        R(i+1)=mod((a*R(i)+c),m);
        A(i+1)=R(i+1)/m;
    end

mean(A)
    
    ans =
    
        0.5345

var(A)
    
    ans =
    
        0.0768

使用MATLAB内置函数rand:

mean(A)
    
    ans =
    
        0.4940
    
    >> var(A)
    
    ans =
    
        0.0835
    
    >>

其实两者相差不大