隨機數大家都會用,但是你知道生成隨機數的演算法嗎?

隨機取樣的件數怎麼算

作者 | 梁唐

頭圖 | CSDN 下載自東方IC

今天我們來和大家聊聊

隨機數

。

大家如果學過程式設計對於隨機數應該都不陌生，應該或多或少都用到過。再不濟我們每週的抽獎都是用隨機數抽出來的，我們用隨機數的時候，往往都會加一個字首，說它是

偽隨機數

，那麼這個偽隨機數的偽字該怎麼解釋，什麼又是真隨機數呢？

真偽隨機數

目前學界劃分真偽隨機數的方式非常簡單，一句話就能說明白，

凡是用一定的演算法使用程式生成的都是偽隨機數

，透過物理現象產生的隨機數才是真隨機數。也就是說計算學家們已經證明了僅僅依靠演算法是無法生成真隨機數的，也可以認為這是一個NP問題。

演算法生成的都是偽隨機數的證明太過複雜我們可以不去深究，但是什麼又叫做物理現象產生的隨機數呢？其實也很簡單，舉個很簡單的例子就是拋硬幣和擲骰子。當然物理現象不止這些，比如還有電子元件的噪音、元素的衰變等等。

真假隨機數之間的最大差別在哪裡？其實

就在是否可以預測上

。計算機演算法得出的各種隨機數之所以是偽隨機數是因為它們的結果都是可以預測的，只要我們知道演算法和起始狀態以及各種引數，就可以預測下一次隨機出來的結果。而真隨機數則無法預測，就是純粹隨機的。

但問題來了，拋硬幣和擲骰子這些物理現象又是真的隨機嗎？如果我們知道了硬幣的起始狀態以及拋擲的角度和力度，是不是可以預測硬幣拋擲的結果呢？進一步我們是否可以假設，如果我們能知道所有例子的所有狀態，是否所有所謂的隨機數都是可以預測的呢？但根據量子力學的測不準原理，我們知道我們無法同時知道粒子的位置和動量，不僅說明了我們無法預測，也說明了我們無法假設預測。

所以某種程度上來說物理現象是不是就是真隨機，這就成了一個哲學問題。但至少在計算機領域當中，這個問題是明確的，演算法得出的都是偽隨機數，只有透過物理現象得出的才是真隨機數。

在計算機系統當中，

偽隨機數都是有周期的

，只要我們持續的次數足夠多，就可以看到這種週期。而真隨機數則不存在這種週期，有一位前輩做過一個隨機數視覺化實驗，也就是把隨機數得到的結果做成圖片。我們可以直觀地對比一下，這是真隨機數視覺化之後的圖片：

看起來像不像是以前的電視收不到訊號的時候顯示的內容？我們再來看看透過演算法生成的偽隨機數視覺化之後的結果：

對比一下還是挺明顯的，明顯可以看出來偽隨機數是有規律的，這個規律體現出來就是影象當中的紋理。如果大家想要獲取真隨機數，可以訪問random。org這個網站，它是免費的，我們可以人為設定上下限來獲取指定範圍內的隨機數。

對比過真偽隨機數之後，我們再來看看現在計算機系統當中常用的偽隨機數生成演算法的原理。

平方取中法

我們首先介紹的是平方取中法，這個方法非常簡單粗暴，是用來產生四位隨機數的。

具體的邏輯是怎樣的呢？首先我們需要一個隨機種子，比如2333，我們把這個隨機種子進行平方，得到5442889。這個數一共有7位，我們給它左邊填充一個0變成05442889，最後取出它的中間四位是4428，這就是我們隨機得到的結果。當我們下次再計算隨機數的時候，隨機數的種子就成了4428。

這個演算法的作者是大名鼎鼎的計算機之父

馮諾依曼

，自從他確定了計算機體系結構之後一直沿用至今。他當時推崇這一演算法的原因很簡單，計算方便，速度快，也容易排查錯誤。它認為如果真的設計一個複雜的演算法來生成看起來比較好的隨機數，可能隱藏的bug比解決的問題還要多。

seed = 2333def random（）： global seed seed = seed ** 2 return int（str（seed）［1：5］）

我寫了程式碼實際運行了一下，結果看起來其實沒有那麼不靠譜。

LCG演算法

馮諾依曼的隨機數演算法雖然看起來簡單，但是非常草率，在很多場合下是顯然不能使用的。所以人們又想出了新的演算法，這個演算法也很簡單，看起來英文縮寫高大上，其實翻譯過來是

線性同餘法

。也就是利用來生成隨機數。

最後返回的結果是上述式子計算之後的結果，abc三個數都是我們選定的引數。當下一次隨機的時候，就將上次的結果作為新的種子進行計算。我們寫出它的遞推公式就是：

這個演算法一眼就看明白了，它的核心完全在於abc這三個引數的選擇。如果選的不好就不能實現隨機數的效果，這裡我給大家分享一個業內常用的選擇，a=25214903917，b=11，c=。這些數不是拍腦袋隨便選的，而是計算學家們算出來的。實際上

Java JDK當中Random的類採用的就是這樣的演算法

。

seed = 2def lcg（）： global seed seed = （25214903917 * seed） & （（1 << 48） - 1） return seed

這種演算法實現方式也非常簡單，並且得到的效果也不錯。如果要增加隨機性，我們還可以在輸出結果上做一些最佳化，比如進行位移或者是調換二進位制位的順序等等。但是這種演算法也有缺點，就是它的計算方式是固定的，只是隨機種子未知。只要願意，

我們是可以透過得到的隨機結果去反推這些引數的。

這並不是一個複雜的演算法，因此LCG演算法得到的隨機數不能應用在一些高安全級別的應用上，否則可能會有安全隱患。

梅森旋轉演算法

LCG演算法實現的偽隨機數效果還不錯，但是週期不夠長，很容易被駭客推算出隨機種子。後來兩個日本學者又研究提出了新的偽隨機數演算法，在這個演算法當中用到了梅森素數，所以稱為梅森旋轉演算法。

簡單介紹一下梅森素數，梅森素數的意思是形如的素數。利用梅森素數的性質可以設計出週期長度為梅森素數長度的隨機數週期。比如目前Python、C++11等語言當中用的隨機數計算包都是用的這種演算法。目前常用的版本週期是，這是一個巨大的天文數字。

梅森旋轉演算法的實現原理非常複雜，網上的資料也不多，我看過一些都不是非常好懂。這裡就不介紹了，大家感興趣可以去了解看看。但我個人覺得意義不大，因為實在是用不到，面試也完全不會考。

雖然梅森旋轉演算法的週期非常非常長，但是仍不是安全的隨機數演算法，仍然有可能會被駭客破解。只不過和LCG演算法相比，被破解的機率以及難度增加了許多。

大家可能很好奇，什麼樣的演算法才是安全的呢？其實業內的安全演算法其實挺取巧的，一般的常用方法就是

利用一個數學界的難題

來設計一個演算法。比如RSA加密演算法，利用的就是大整數因式分解的問題。這樣的問題業內除了暴力計算沒有好方法，而暴力計算的複雜度非常非常高，根本不可能在有限時間內有解，自然這個就是一個安全的演算法了。如果某位駭客有能力設計出破解的演算法來，他根本也不用破解啥，只要把解法發表成論文，自然可以名利雙收。

你看隨機數這麼一個常見的功能下面居然隱藏了這麼深的科學原理，而且更加震驚的是以我們人類如此厲害的文明，居然連隨機一個數都做不到。不知道大家看到這裡又有何種感受呢？

更多精彩推薦

300億美元，AMD為什麼要買Xilinx？

1024程式設計師節開源技術英雄會，參會“英雄榜”發榜

5行Python程式碼實現刷爆全網的動態條形圖！

如何應對雲原生之旅中的安全挑戰？

採摘工人月薪十萬卻無人應聘，英澳農場求助 AI

區塊鏈+生鮮：杜絕“偷樑換柱”和“以次充好”

點分享

點點贊

點在看