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

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

它的首要條件便是必須符合平均分配率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++的方式當作亂數用(連結中有教學)