我們人在需要一個隨機數字的時候,我們是可以透過擲骰子的方式來取得 ( 雖然在現實生活中我們沒有辦法控制所有會影響骰子的變數,但只要骰子是公平的,我們就可以相信得到的數字是足夠隨機的。) 那麼電腦到底要怎麼去得到一個隨機數字呢? 亂數( Random Number ) 一直以來,都是一名工程師在做程式設計的時候,十分常見的需求! 不論是在設計有趣的電玩遊戲;還是高深複雜的密碼學;或近幾年越來越火紅的人工智慧;以及 Jason 在上一篇介紹的【演算法】蒙地卡羅模擬 Monte Carlo Simulation 等等,其背後都需要仰賴一個好的隨機亂數產生算法,你或也能說 "隨機亂數產生演算法 Random Number Generation Algorithm" 幫忙建構了我們這個世界。 但可惜的是,目前還沒有真正完全隨機的亂數產生算法問世。 所以基本上我們現在所用的都是偽隨機 ( Pseudorandomness )[註一] 亂數產生器,一般來說偽隨機的函式有分週期性與非週期性的。理論上使用非週期性的函式會比使用週期性的函式好,但是週期性的函式在計算上往往是比較快的,而且可以透過調整週期性函式的一些係數,使得週期性函式的週期變得很大很大,來達到與使用非週期性函式一樣的效果。所以在實作上我們一般還是使用週期性的隨機函數! 然後有一點我們要知道的是,一般電腦採用的是"決定性"的計算模型: 即同一筆資料配合相同的計算過程 ( Function ),最後必定會得到相同的結果( outcome )。
為了達到每次都能夠有不同的輸出,我們每次就要提供給它(Function) 不同的輸入。但是我們往往沒有辦法一直新的 data 可以餵給它,更何況我們今天要的是一個亂數產生器,如果我餵給它的資料集是 S{x,x,x,x,x,x...},那麼由於我每次餵進去的資料是一樣的,輸出的結果也會是一樣的,就沒辦法正確的產生亂數。
所以我們會採用回授(feedback)的方式,把這次計算的輸出結果當作下次的輸入使用。
由於上述的特性,所以在Computer Science 裡會我們會習慣將偽隨機數表示成遞迴定義的數列。
說到遞迴定義的數列,一般第一印象會想到的大概是 Fibonacci 費式數列吧~ ㄜ.. 至少對資工系的學生來講是這樣啦xD 一般人應該在 國/高中數學裡也看過這個東西,長的像這樣:1、1、2、3、5、8... ,也稱作黃金分割數列。
而費式數列用遞迴定義表示的時候會寫成這樣:F(n) = F(n-1) + F(n-2)。
這時候如果我們幫 Function 設定一個最大的輸出限制 RAND_MAX,設 RAND_MAX = 64 好了,我們讓 Fibonacci 超過 RAND_MAX 折回來(即取餘數),的時候數列會長的像怎樣呢? F(n) = ( F(n-1) + F(n-2) ) mod RAND_MAX 1、1、2、3、5、8、13、21、34、55、25、16、41、57... 可以發現在做完 mod 以後數列的規則就不太明顯了,如果這時候我們再加上一點變化呢? 例如改變input 的項次 e.g. F(n) = ( F(n-2) + F(n-4) ) mod RAND_MAX ,然後前四項我們給它 1、2、4、8 做初始值好了。 1、2、4、8、9、11、15、23、32、43、58、17、49、28、22... 你會發現經過這樣的變化,數列的規則已經很難被我們一眼看穿了。而其實這樣的設計,就是常見的一類偽隨機數產生器,稱作:延遲費氏數列 ( Lagged Fibonacci )。 不過在實務上,我們更常使用基於「線性同餘法 Linear Congruential Method」的偽線性隨機數產生器。 可表示成:X(n) = ( a * X(n-1) + b ) mod RAND_MAX 像在 C Language 中內建的亂數產生器 rand() 使用的就是基於線性同餘原理,實現代碼如下:
Random Function
但是一個好的隨機亂數產生演算法,除了要不容易被預測之外,還有另一個重點就是我們希望它的分佈要足夠平均 ( 呈現 uniform distribution[註二] )。
那我們來看看 C Language 內建的 rand() 函數在這方邊的表現如何吧! ( 這部分我直接拿【影像處理】灰階直方圖均化 Histogram Equalization 那篇的程式來改 )
這是 N=50000 的統計結果,你可以發現其實它分佈的沒有很理想,這也是為什麼 C++11 會將包含 Mersenne Twister 在內的多種亂數引擎納進標準。
由於偽亂數不是真的隨機亂數,在有些方面它們不能被使用,例如在密碼學中使用偽亂數要極為小心! 避免因為其可計算性的部分而被用來攻擊。包括之前介紹的蒙特卡羅方法,在使用的偽亂數上也必須挑選週期極長、隨機性夠高的隨機函式,以確保計算結果有足夠的隨機性。 這部分像 Jason 先前在介紹蒙特卡羅方法那篇實作上就很偷懶,直接 call C 內建的 rand() 函數來用,你就會發現即便以N 已經設置的很大了,模擬出來的效果還是不夠好 >"< 雖然現在仍沒有真正完全的隨機亂數產生算法可以使用,但是我們還是可以透過一些專門的裝置,比如熱噪訊號、量子力學的效應、放射性元素的衰退輻射,或使用無法預測的現象,譬如用戶按鍵盤的位置與速度、用戶運動滑鼠的路徑坐標等等來產生真正的隨機亂數。 Ok, 那我們這篇就介紹到這邊八,感謝各位。
[註一] 偽隨機( Pseudorandomness ):意思是過程似乎是隨機的,但實際上並不是。例如偽亂數是使用一個確定性的演算法計算出來的似乎是隨機的數序,因此偽亂數實際上並不隨機。
[註二] Uniform Distribution:均勻分佈,在範圍(a,b)內出現的機會均等。
0 評論
發表回覆。 |
Jason Chen人不光是生來就擁有一切,而是靠他從學習中得到的一切來造就自己。- 歌德 文章分類
全部
封存檔
九月 2023
|