電腦生成的隨機數是真的隨機數嗎?

電腦在製造數列時需要特定的程序及演算法。由於隨機數「不存在決定下一個數字的規律」,因此,電腦按照特定程序等規律生成的數列不能算是真正意義上的隨機數。

但在實際應用中,它們可以替代真正的隨機數,或者更恰當的說法是,它們是可以被當成隨機數的「偽隨機數」。

首次研究偽隨機數的是電腦之父、匈牙利數學家約翰·馮·諾伊曼(John von Neumann,1903~1957)。馮·諾伊曼研究的「平方取中法」是最早的偽隨機生成法。

「平方取中法」是最早的偽隨機生成法

約翰·馮·諾伊曼,製造了現代計算機的原型。他的研究影響了從電腦遊戲理論到原子彈開發等廣泛領域。

以下是馮·諾伊曼研究的最早的偽隨機數生成演算法——「平方取中法」和現在依然在使用的「線性同餘法」。

平方取中法(4位數的情況下)

取一個4位數作為「種子」(隨機數的種子,在例子中為有下劃線的1234)。種子進行平方操作後得到一個八位數(不足八位的在前面用0補足),取這個八位數的中間4位(5227)作為第一個偽隨機數。然後將這個數(5227)按照相同的操作得出下一個偽隨機數(3215)。重複以上操作不斷得出偽隨機數的方法稱為平方取中法。

線性同餘法(4位數的情況下)

線性同餘法(4位數的情況下)

將種子(例子中為有下劃線的1234)乘以事先決定好的的定數(例子中為567),然後加上另一個定數(例子中為89)得到一個數字(699767)。將這個數字除以一個定數(例子中為9773),然後求餘數。把這個餘數(1657)作為第一個偽隨機數。將這個1657按照相同操作得到下一個偽隨機數(2146)。重複以上操作不斷得出偽隨機數的方法稱為線性同餘法。在加式中使用的定數為0時稱為「乘同餘法」。

在馮·諾伊曼之後又開發了以「線性同餘法」為首的各種偽隨機數生成法。偽隨機數的好壞取決於它和 「真正的隨機數的接近程度」以及自身的「生成速度」。目前,公認最好的偽隨機數生成演算法是全世界程式設計師廣泛使用的、由日本廣島大學松本真教授和日本山形大學西村拓土副教授於1998年研發出的「梅森旋轉演算法」。要理解這個演算法需要向量和矩陣等數學知識,因而在此不做詳細介紹,這一演算法巧妙利用了「梅森素數」的特殊性質。

梅森旋轉演算法

下圖的三維空間內有(231—1)個點,每個點的座標來自使用線性同餘法生成的3個偽隨機數。從這些點上可以看到規則的紋樣或間隙。右圖則是使用梅森旋轉演算法得到的點配置相同個數的結果,並不能看出有規律的紋樣或間隙。

當然,使用這種方法生成的隨機數也只是偽隨機數,並不是「真正的隨機數」。偽隨機數之父馮·諾伊曼曾說過:「使用公式製造隨機數,從某種意義上來說是犯罪。」

來源:科學世界

相關文章

打破對稱性帶來的驚喜

打破對稱性帶來的驚喜

1911年,物理學家海克·卡末林·昂內絲(Heike Kamerlingh Onnes)最早注意到了超導現象。它起初被認為僅僅代表了一種科學...