\( \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~m-1之間的每個數字, 出現的機率必須相等。
Linear Congruential Method雖是常用法,但也有它的條件:
X(n+1) = (a*X(n) + c) mod 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 則留言: