【演算法】隨機亂數產生Random Number Generation

但可惜的是，目前還沒有真正完全隨機的亂數產生算法問世。

所以基本上我們現在所用的都是偽隨機( Pseudorandomness )[註一] 亂數產生器，一般來說偽隨機的 ... JasonChen'sBlog Home About Press Contact Home About Press Contact 【演算法】隨機亂數產生RandomNumberGeneration 1/25/2019 0評論   我們人在需要一個隨機數字的時候，我們是可以透過擲骰子的方式來取得(雖然在現實生活中我們沒有辦法控制所有會影響骰子的變數，但只要骰子是公平的，我們就可以相信得到的數字是足夠隨機的。

)那麼電腦到底要怎麼去得到一個隨機數字呢？ 亂數(RandomNumber)一直以來，都是一名工程師在做程式設計的時候，十分常見的需求！ 不論是在設計有趣的電玩遊戲；還是高深複雜的密碼學；或近幾年越來越火紅的人工智慧；以及Jason在上一篇介紹的【演算法】蒙地卡羅模擬MonteCarloSimulation等等，其背後都需要仰賴一個好的隨機亂數產生算法，你或也能說"隨機亂數產生演算法RandomNumberGenerationAlgorithm"幫忙建構了我們這個世界。

但可惜的是，目前還沒有真正完全隨機的亂數產生算法問世。

所以基本上我們現在所用的都是偽隨機(Pseudorandomness)[註一]亂數產生器，一般來說偽隨機的函式有分週期性與非週期性的。

理論上使用非週期性的函式會比使用週期性的函式好，但是週期性的函式在計算上往往是比較快的，而且可以透過調整週期性函式的一些係數，使得週期性函式的週期變得很大很大，來達到與使用非週期性函式一樣的效果。

所以在實作上我們一般還是使用週期性的隨機函數！ 然後有一點我們要知道的是，一般電腦採用的是"決定性"的計算模型： 即同一筆資料配合相同的計算過程(Function)，最後必定會得到相同的結果(outcome)。

為了達到每次都能夠有不同的輸出，我們每次就要提供給它(Function)不同的輸入。

但是我們往往沒有辦法一直新的data可以餵給它，更何況我們今天要的是一個亂數產生器，如果我餵給它的資料集是S{x,x,x,x,x,x...}，那麼由於我每次餵進去的資料是一樣的，輸出的結果也會是一樣的，就沒辦法正確的產生亂數。

所以我們會採用回授(feedback)的方式，把這次計算的輸出結果當作下次的輸入使用。

由於上述的特性，所以在ComputerScience裡會我們會習慣將偽隨機數表示成遞迴定義的數列。

說到遞迴定義的數列，一般第一印象會想到的大概是 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))modRAND_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))modRAND_MAX，然後前四項我們給它1、2、4、8做初始值好了。

1、2、4、8、9、11、15、23、32、43、58、17、49、28、22... 你會發現經過這樣的變化，數列的規則已經很難被我們一眼看穿了。

而其實這樣的設計，就是常見的一類偽隨機數產生器，稱作：延遲費氏數列(LaggedFibonacci)。

不過在實務上，我們更常使用基於「線性同餘法 LinearCongruential  Method」的偽線性隨機數產生器。

可表示成：X(n)=(a*X(n-1)+b)modRAND_MAX 像在CLanguage中內建的亂數產生器rand()使用的就是基於線性同餘原理，實現代碼如下： 但是一個好的隨機亂數產生演算法，除了要不容易被預測之外，還有另一個重點就是我們希望它的分佈要足夠平均(呈現uniformdistribution[註二])。

那我們來看看CLanguage內建的rand()函數在這方邊的表現如何吧！ (這部分我直接拿【影像處理】灰階直方圖均化HistogramEqualization 那篇的程式來改) 這是N=50000的統計結果，你可以發現其實它分佈的沒有很理想，這也是為什麼 C++11會將包含MersenneTwister在內的多種亂數引擎納進標準。

由於偽亂數不是真的隨機亂數，在有些方面它們不能被使用，例如在密碼學中使用偽亂數要極為小心！ ​避免因為其可計算性的部分而被用來攻擊。

包括之前介紹的蒙特卡羅方法，在使用的偽亂數上也必須挑選週期極長、隨機性夠高的隨機函式，以確保計算結果有足夠的隨機性。

這部分像Jason先前在介紹蒙特卡羅方法那篇實作上就很偷懶，直接callC內建的rand()函數來用，你就會發現即便以N已經設置的很大了，模擬出來的效果還是不夠好>"< 雖然現在仍沒有真正完全的隨機亂數產生算法可以使用，但是我們還是可以透過一些專門的裝置，比如熱噪訊號、量子力學的效應、放射性元素的衰退輻射，或使用無法預測的現象，譬如用戶按鍵盤的位置與速度、用戶運動滑鼠的路徑坐標等等來產生真正的隨機亂數。

Ok,那我們這篇就介紹到這邊八，感謝各位。

[註一]偽隨機(Pseudorandomness)：意思是過程似乎是隨機的，但實際上並不是。

例如偽亂數是使用一個確定性的演算法計算出來的似乎是隨機的數序，因此偽亂數實際上並不隨機。

​ [註二]UniformDistribution：均勻分佈，在範圍(a,b)內出現的機會均等。

0評論 發表回覆。

JasonChen 如果說懷才就像懷孕，時間久了才能讓人看出來。

那麼還有另一個相似的點就是..在開花結果之前，都要先給人幹到不要不要的Q_Q 文章分類 全部 介紹 分享 加密貨幣Cryptocurrency 影像處理DIP 教學 消息 演算法Algorithm 物聯網IoT 資料科學DataScience 遊戲Game 閒聊 封存檔 三月2022 八月2021 七月2021 六月2021 五月2021 四月2021 三月2021 二月2021 一月2021 十二月2020 十一月2020 十月2020 九月2020 八月2020 七月2020 四月2020 三月2020 二月2020 一月2020 十二月2019 十一月2019 十月2019 九月2019 八月2019 七月2019 六月2019 五月2019 四月2019 三月2019 二月2019 一月2019 十二月2018 十一月2018 十月2018 九月2018 八月2018 七月2018 六月2018 五月2018 四月2018 三月2018 二月2018 一月2018 十二月2017 十一月2017 十月2017 RSS訂閱 提供者 使用自訂式範本建立您的專屬獨特網站。

開始吧