[ Mersenne Twister ] 梅森旋轉算法

梅森旋轉算法是一種可以快速產生高級偽隨機數的算法，修正了很多以前的隨機速算法的缺陷(Ex:線性同於算法)。

這是專門用在蒙地卡羅測試用的，不要拿它來做持久化隨機二叉數的亂數產生器，會太慢

最為廣泛使用Mersenne Twister的一種變體是MT19937，可以產生32位整數序列，從C++11開始，C++也可以使用這種算法。在Boost C++,Glib和NAG數值庫中，作為插件提供。但是一般在競賽時可能會有不支援的情況發生，所以將它做成模板當作參考。

MT19937_64則是可以產生64位整數序列

以下提供模板:

	#ifndef SUNMOON_MERSENNE_TWISTER
	#define SUNMOON_MERSENNE_TWISTER
	template<typename T,T w,int n,T m,T r,T a,T u,T d,T s,T b,T t,T c,T l,T f>
	class mersenne_twister{
	private:
	int index;
	const T lower_mask=(1ull<<r)-1ull;
	const T upper_mask=~lower_mask;
	T mt[n];
	inline void twist(){
	for(int i=0;i<n;++i){
	T y=(mt[i]&upper_mask)+(mt[(i+1)%n]&lower_mask);
	mt[i]=mt[(i+m)%n]^y>>1;
	if(y%2!=0)mt[i]=mt[i]^a;
	}
	index=0;
	}
	public:
	mersenne_twister(T seed):index(n){
	mt[0]=seed;
	for(int i=1;i<n;++i)mt[i]=f*(mt[i-1]^mt[i-1]>>(w-2))+i;
	}
	inline T operator()(){
	if(index>=n)twist();
	T y=mt[index++];
	y=y^y>>u&d;
	y=y^y<<s&b;
	y=y^y<<t&c;
	y=y^y>>l;
	return y;
	}
	};
	typedef mersenne_twister<unsigned,32,624,397,31,0x9908b0dfUL,11,
	0xffffffffUL,7,0x9d2c5680UL,15,0xefc60000UL,18,1812433253UL> MT19937;
	typedef mersenne_twister<unsigned long long,64,312,156,31,0xb5026f5aa96619e9ULL,29,0x5555555555555555ULL
	,17,0x71d67fffeda60000ULL,37,0xfff7eee000000000ULL,43,6364136223846793005ULL> MT19937_64;
	#endif

view raw mersenne_twister.cpp hosted with ❤ by GitHub