計算機的隨機數是怎麼產生的？有演算法嗎？如果有演算法，那麼產生的數字還是真真意義的隨機數嗎？

01-28

現代計算機中的隨機數都是用演算法產生的偽隨機數（偽隨機性）。這些演算法本質上都是確定性的，給定一個輸入就會有一個固定的可預測的輸出，因此產生的數都不是真正意義上的隨機數。

具體演算法包括平方取中法、乘積取中法、加同餘法、乘同餘法、乘加同餘法、梅森旋轉法等。其中最常用的是乘加同餘法（又稱「線性同餘法「，長期以來被視作生成偽隨機數的」標準「演算法），最新的是梅森旋轉法（1997年提出，現已加入C++11豪華午餐）。此外，還有一些比較特（qi）別（pa）的偽隨機數演算法，比如Stephen Wolfram大神的Rule 30，在Mathematica中就可以用這個Rule 30來生成偽隨機數。因為這些演算法都是確定性的，所以偽隨機數發生器的第一個輸入就尤為重要，這第一個輸入被稱為」種子「（seed）。在相同的演算法、相同的配置下，相同的種子將產生相同的隨機數序列，這就是為什麼你在學C/C++時老師會告訴你在程序中首次調用rand()函數之前務必要有一行srand((int)time(0));

事實上的確有可以產生真隨機數的方法，主要包括隨機數表法和物理法：前者是記錄大量隨機實驗的結果並將其整理成表以備使用；後者則是將某些放射性同位素的衰變事件或者電子計算機的固有雜訊作為產生隨機數的物理源。這兩類方法的缺點也顯而易見：前者需要耗費大量人力物力進行隨機實驗，並且其結果需佔用大量存儲空間；後者則需要在計算機上添加特殊裝備，更不用提放射性核素的獲取管理以及很多人對「放射性」根深蒂固的恐懼。

總之經過數十年的實踐，人們最終還是選擇了偽隨機數，因為其原理簡單、耗費資源少、產生隨機數的成本低；當然，為了保證偽隨機數足夠「隨機」，人們會對其做大量校核，相關的專家學者也會不斷研究更好的偽隨機數產生演算法。

這是我們演算法課上講的一點東西，產生隨機數是有演算法的！

Linear Congruential GeneratorWhen you use rand() in C/C++, they arent really random numbers, it is a string of numbers that is based on a formula in the standard library.

A linear congruential generator is a popular random number generator:

X(n+1) = (a * X(n) + c) mod m

where:

a: 0 &< a &< m
c: 0 &<= c &< m
X(0): 0 &< m

Requirements of c, a, and m:

c and m should be relatively prime (the only positive integer that evenly divides them both is one)
- "For example, 14 and 15 are coprime, being commonly divisible by only 1, but 14 and 21 are not, because they are both divisible by 7." [2]
a - 1 must be divisible by all prime factors of m
a - 1 must be a multiple of 4 if m is a multiple of 4

glibc (used by gcc) uses these parameters:

m = 2^32
a = 1103515245
c = 12345

Visual C/C++ and Apple CarbonLib use a linear congruential generator too.

This means I should be able to perfectly predict the random numbers coming from a gcc rand function if I know the seed or the previous random number output.

In fact, in the "Berkley Open Infrastructure for Network Computing" (BOINC), they save the state of the random number generator by saving off the last random number generated. Then to restore, that number is put in as the seed.

一般比較懶的都是演算法生成的偽隨機數。但也有的處理器有生成隨機數指令的，還有一些專門的隨機數生成設備，這些就屬於利用自然界的真隨機數了。

還有一種有趣的方法是把用戶的行為比如滑鼠軌跡進行編碼從而生成隨機數的，這種聽起來也是真隨機數。

至於演算法產生的為隨機數能不能用，還是要分情況。比如梅森旋轉數是很好的均勻分布偽隨機數，用於蒙特卡羅模擬是可以的。但是因為它是確定性的，所以用作一些加密演算法中要求的隨機數序列就不可以了。