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

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

它的首要條件便是必須符合平均分配率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的倍數。

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

以下是在網路上找到的一些不錯的亂數產生方法:

	//線性同餘方法
	//這個方法數字很好記
	unsigned random1(){
	static unsigned x=20150118;
	return x=x*0xdefaced+1;
	}
	int random2(){
	static unsigned x=time(0);
	return x=x*16807;//7^5
	}
	// 網路上看到的，用來處理treap的亂數
	int random3(){
	static int x=123456789;
	return x+=(x<<2)+1;
	}
	long long random4(){
	static long long x=323232;
	return x+=x<<2|1;
	}
	//5、6是較快的算法，利用簡單的移位處理
	inline int random5(){
	static int seed=20160424;
	return seed+=(seed<<16)+0x1db3d743;
	}
	inline long long random6(){
	static long long seed=20160424;
	return seed+=(seed<<32)+0xdb3d742c265539d;
	}
	//要記數字太麻煩了而且比較慢，比賽時不要用這種
	int random7(){
	static int x=1;
	return x=x*1103515245+12345;
	}

view raw lehmer random.cpp hosted with ❤ by GitHub

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