SICP中1.2.6素數檢驗一節(jié)中采用概率算法，通過隨機抽樣的方法利用費馬小定理測試來檢驗給出的整數是否為素數。這里需要用到隨機數生成的方法(random n)，即：隨機返回0到n之間的任意整數，而我用的Calysto Scheme Kernel恰好沒有相應的隨機數生成方法的實現(xiàn)。之前有遇到Matlab進行隨機模擬的時候，由于沒有設定seed，導致運行了很久的程序一直在周期性地重復固定的“隨機數”，剛好借此機會研究一下隨機數生成的原理及方法。

計算機生成隨機數的方法一般是采用數學法，即根據某一(遞推)公式產生一個周期性足夠大的數列，滿足一定的均勻分布的特性，其優(yōu)點在于可以迅速產生大量偽隨機數，缺點是所產生的并非真正的隨機數，只是近似隨機。不同的公式能夠產生性質不同的偽隨機數(列)，一種簡單常用的方法稱為線性同余發(fā)生器(Linear Congruence Generator, LCG)，其公式如下：

$$

\begin{cases}

X_0 = SEED, & \text{設定初始值}\\X_n = (A * X_{n-1} + B) (Mod M)\\ R_n = X_n/M

\end{cases}

$$

顯然LCG方法產生的隨機數列周期小于$M$，同時在保證周期盡量大的情況下，還需要適時地重設初始值，一般以系統(tǒng)時間作為“種子”設定初始值。Scheme的實現(xiàn)如下，假設將常量設定為 $A = 3, B = 0, M = 5$：

;; random.scm

(define SEED 1)

(define (seed i) (set! SEED i))

(define A 3)

(define B 0)

(define M 5)

(define (LCG)

(begin

(seed (remainder (+ (* A SEED) B) M))

SEED))

(define (random n)

(round (* (/ (LCG) (- M 1)) n) ))

將初始值設定為系統(tǒng)時間后，檢驗10次$[0, 100]$隨機數產生結果：

;; test your random

(define (test-rands n)

(if (= n 0)

(display "Done!")

(begin

(display (random 100))

(newline)

(test-rands (- n 1)))))

(seed (round (current-time)))

(test-rands 10)

;; 75

;; 100

;; 50

;; 25

;; 75

;; 100

;; 50

;; 25

;; 75

;; 100

;; Done!

可以發(fā)現(xiàn)，在$A = 3, B = 0, M = 5$的條件下，LCG產生的隨機數列周期僅為4，若要得到最大周期，需要滿足：

$B, M$互質；

$M$的所有質因數都能整除$A-1$；

若$M$是4的倍數，$A-1$也是；

$A,B,X_0$都比$M$小；

$A,B$是正整數。

參考

總結

以上是生活随笔為你收集整理的matlab线性同余发生器,线性同余法生成伪随机数的全部內容，希望文章能夠幫你解決所遇到的問題。

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