線性同餘發生器

線性同餘發生器（Linear congruential generator），簡稱LCG，是一種能產生具有不連續計算的偽隨機序列的分段線性方程的算法，它代表了最古老和最知名的偽隨機序列生成器算法之一，其理論相對容易理解，並且易於實現和快速，特別是在可以通過存儲位截斷提供模運算的計算機硬體上。

基本介紹

• 中文名：線性同餘發生器
• 外文名：Linear congruential generator
• 實質：偽隨機序列生成器
• 簡稱：LCG

簡介

線性同餘發生器（LCG）是一種偽隨機序列生成器算法，能產生具有不連續計算的偽隨機序列的分段線性方程。生成器由循環關係定義：

這裡，（1） 是偽隨機序列；

（2） 表示模量；

（3） 表示乘數；

（4） 表示增量；

（5） 表示初始值。

是指定生成器的整數常量。如果 ，該發生器通常稱為乘法同餘發生器（MCG）。如果 ，該發生器稱為混契約余發生器。

區間長度

線性同餘發生器的好處是，通過適當選擇參數，區間長度可知且很長。雖然不是唯一標準，但是一般情況下太短的區間長度在偽隨機數發生器中是一個致命的缺陷。

雖然LCG能夠產生偽隨機數，且可以通過正規的隨機性測試，但它對參數 和 的選擇極為敏感。例如， 和 產生一個簡單的進制計數器，它具有長的周期，但顯然非隨機。

參數選擇常見的有三種：（1）為素數， ；（2）為2的冪， ；（3） 。

優缺點

線性同餘發生器速度快，且需要較少的存儲器保留狀態，這使其對於模擬多個獨立流非常有用。

線性同餘發生器特有的一個缺陷是，如果用於選擇n維空間中的點，那么這些點至多會位於 超平面。這是由於序列的連續值之間的序列相關性。草率選擇地乘法器通常會有較少間距平面，易出問題。光譜測試是LCG質量的一個簡單測試，測量區間長度和可選擇的乘數。

LCG特有的另一個缺陷是當為2的冪時，低階比特周期較短。這種情況可以通過使用大於所需輸出的模數，並使用狀態的最高有效比特來減輕。

LCG不可用於加密應用程式，或為這些應用程式使用密碼安全的偽隨機數生成器。然而，對於某些套用，LCG可能是一個不錯的選擇。例如，在嵌入式系統中，可用記憶體量通常受到嚴格限制。同樣，在諸如視頻遊戲機這樣的環境中，只需要一小部分LCG的高階位就足夠了。