了解計算機如何生成隨機數

偽隨機數生成器（PRNG）

具有任何編程經驗的人都知道計算機是確定性機器。如果你提供相同的輸入，則將始終獲得相同的輸出。這就是為什么讓計算機偶然生成隨機數比看起來復雜的多。

隨機數應用在密碼學到博彩，視頻游戲等很多行業。但是，計算機天生就不能隨機。相反，程序員依靠偽隨機數生成器（PRNG），從稱為種子/seed的給定起始值以編程方式生成新的隨機數。

這些算法有其自身的局限性。由于隨機數是通過程序生成的，因此，如果有人能夠識別出使用的種子值和PRNG算法，他們將能夠預測序列中的下一個隨機數。這將使攻擊者可以解密，預測序列中的下一張紙牌，在視頻游戲中作弊等。

但是PRNG在涉及建模和仿真的情況下仍然非常有用，因為它允許通過使用相同的種子初始化隨機數生成器來“重播”一系列隨機事件。

“真”隨機數生成器（TRNG）

在隨機性第一的場景下，我們使用“真”隨機數生成器（TRNG）。與具有任意種子值的PRNG不同，TRNG從其環境/外部數據中選擇一個種子值。

以下是一些潛在的選擇：

鼠標動作
風扇噪音
氣壓
自上一整秒以來的微秒數

只需要選擇攻擊者無法預測的種子即可。然后，該種子值將被傳遞到類似于PRNG的算法中，該算法將生成一個隨機數。

兩種方法之間的實際差異。

PRNG比TRNG更快，PRNG的確定性在你要重播一系列“隨機”事件的情況下非常有用。

此外，某些PRNG算出的隨機數，本質上是周期性的，有一定的確定概率，但是使用好的初始化參數的現代PRNG，這個周期可以足夠長。

相反，TRNG比PRNG慢，沒有確定性，并且不是周期性的。

線性同余生成器

實現一個簡單的PRNG。一個稱為線性同余生成器（LCG）算法的變體。LCG以前是最常用和研究最多的PRNG之一（https://en.wikipedia.org/wiki/Linear_congruential_generator）。

這是LCG的迭代算法：

LCG上的Wikipedia頁面（https://en.wikipedia.org/wiki/Linear_congruential_generator）記錄了一些常用的模數m，乘數a和增量值c。關于最佳值的建議尚無統一看法，因此各個實現之間存在不同的值。

我們必須注意這些參數的取值。選擇錯誤的值可能會導致創建一個過短的周期，從而使我們的隨機數生成器無用。

在下圖中，可以看到對參數的微小更改會極大地影響周期長度。

代碼實現

這里使用早期C語言標準（C90 / C99 / ANSI C和C11）中記錄的值。

a = 1103515245

m = 2³¹

c = 12345

無論選擇哪種PRNG算法，都應導致隨機數的均勻分布和足夠長的時間。

import Foundation
final class LCG{
  	static func generate(modulus: Int, multiplier: Int, increment: Int, seed: Int) -> Int {
      return (multiplier * seed + increment) % modulus
    } // Generating 100 random numbers using LCG var seed = 0for _ in 0..<100 { let randomNumber = LCG.generate(modulus: 2147483648, multiplier: 1103515245, increment: 12345, seed: seed) seed = randomNumber print(randomNumber)}

模擬扔骰子

假設你要模擬骰子投擲。github地址：

https://gist.github.com/aryamansharda/070d508ee6c61d168d06d5aea9ecf946#file-linearcongruentialgenerator-dice-swift

將模數設置為6似乎很合理，但這會導致周期太短而無法使用。所以這里需要對最后的隨機數結果取模6處理。

var seed = 0
for _ in 1...40000 {
  let randomNumber = LCG.generate(modulus: 2147483648, multiplier: 1103515245, increment: 12345, seed: seed)
  seed = randomNumber
    let diceRoll = 1 + (randomNumber % 6)
  print(diceRoll)
}

使用上面的代碼，模擬40,000次骰子擲骰，查看結果，可以看到結果確實是均勻分布。