\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年1月17日 星期六

[ 線性同餘方法 ] 亂數產生器 實做

今天來講幾個簡單的亂數產生方法
主要是利用線性同餘方法來處理的

它的首要條件便是必須符合平均分配率Uniform distribution,也就是在$0 \sim m-1$之間的每個數字, 出現的機率必須相等。
Linear Congruential Method雖是常用法,但也有它的條件:
$X(n+1) = (a \times X(n) + c) \%m$,其中$\%$是取餘數的意思
$X(n+1)$為新的亂數,$X(n)$為前一次產生的亂數。則各參數必須符合下列條件:

  1. $c$與$m$必須互質。
  2. 對於任何$m$的質因數$p$,也必須為$a-1$的質因數。
  3. 若$m$為$4$的倍數,則$a-1$也必須為4的倍數。


如此才能確保產生出來的亂數符合平均分配率,同時也具有最長的重複週期。

以下是在網路上找到的一些不錯的亂數產生方法:
其中random1是Brain大神在處理randomize binary tree的亂數(0xdefaced是質數,defaced是英文單字比較好記)
random2聽說是stdlib裡面的rand()原型,而16807是7的5次方,random2可以產生較rand()大的亂數
random4不是線性同於方法,個人覺得他比較像Subtract with carry的方法
在做[分裂/合併式]randomize binary tree時,其實可以利用seed++的方式當作亂數用(連結中有教學)

4 則留言: