現在的隨機函數發生器大都采用的是線性同余法。

?

同余的概念是這樣描述的：

設m是一個給定的正整數，如果兩個整數a，b用m除，所得的余數相同，則稱a，b對模m同余。

所謂線性同余法（又叫混合同余法），就是這樣的一個公式：X[i+1]=(A*X[i]+C) mod M；

經前人研究表明，在M=2^q的條件下，參數A，C，X[0]按如下選取，周期較大，概率統計特性好:

A=2^b+1=2^(log2(M)/2)+1=2^log2(sqrt(M))+1=sqrt(M)+1；b取q/2 附近的數

C=(1/2+sqrt(3))*M

X[0]為任意非負數

M ， 模數???????? 0 < M
A， 乘數???????? 0 <= A<M
C， 增量???????? 0 <=C<M
Xi，開始值??????? 0<=Xi<M

它的一個致命的弱點，那就是隨機數的生成在某一周期內成線性增長的趨勢，顯然，在大多數場合，這種極富“規律”型的隨機數是不應當使用的。

?

同余序列總是進入一個循環，這是一個事實，它最終必定在N個數之間無休止的重復循環。
使用該方法產生的偽隨機數能不能近似真正的隨機效果，跟四個整數的設置相關：
1.???????? 序列的開始值，一般取正整數。
2.???????? m：一個同余序列的周期不可能多于m個元素，所以，為了達到預期的隨機效果，一般我們希望這個值稍稍大一點。在大多數情況下，當m = 2e（e表示計算機的字大小）時，在計算機中得到的隨機效果就比較令人滿意了。而且這樣對于隨機數生成速度也是比較合理的。
3.???????? a：當a=1的時候，Xn=（X0+nc）mod m ，它不具有隨機序列的特性；而當a=0的時候甚至更糟糕。因此，為實用起見，選擇2 <= a<m比較合理。
4.???????? c：當c=0時，數的生成過程比c！=0的時候要稍微快些，它的限制縮短了這個序列的周期長度，但是也仍然有可能得到一個相當長的周期。當c=0時被稱為乘同余法，c！=0稱為混合同余法。為了一般性，我建議選擇采用混合同余法。
由m，a，c和X0所定義的線形同余序列得到最大的周期長度m的條件如下：
當且僅當

（1）c與m互素。
（2）對于整除m的每個素數p，2^b=a-1是p的倍數。
（3）如果m是4的倍數，則b也是4的倍數。
就像開始提到的，偽隨機數的產生都是由一個起始種子數開始的，上面描述的就是由一個種子數下能夠產生的隨機數的序列。這個序列的周期性是必然的，當這個周期能夠滿足預期的效果的時候，就是我們看到的滿意的隨機效果。
在確定初始種子數的時候，可以有多種形式，例如將某時刻的時鐘數據做種子，通過時間的不停變化，進行隨機數的求取來達到隨機效果。這些都是方法問題了，不在算法討論范疇。

總結

以上是生活随笔為你收集整理的线性同余法[纯理论]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。