在Android开发中用到的MT随机数生成器

把以前的AS3移植版略改了一下，目前正用在jkanji中。测试过一段时间，貌似没什么bug。做过一个最简单的硬币测试，在相同种子的情况下正反面次数是差不多。不过以前看过一本书说MT算法不是最好的，而且网上有很多实现，我只是让它的计算结果尽可能接近于原来的C版本。

官网介绍在：

Mersenne Twister Home Page

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html

 

实现和测试代码在同一个类中，见下：

 

package com.iteye.weimingtom.jkanji;

/**
 * Mersenne Twister with improved initialization (2002)
 * @see http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/mt19937ar.html
 * @see http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c
 * 
 * changed:
 * 		1. init_genrand: mt[mti], add temp
 * 		2. >>: >>>
 * 		3. uint => int
 * 		4. long genrand_int32()
 * 		5. y & 0xffffffffL
 */
public class MersenneTwisterRandom {
	private static final int N = 624;
	private static final int M = 397;
	private static final int MATRIX_A = 0x9908b0df;
	private static final int UPPER_MASK = 0x80000000;
	private static final int LOWER_MASK = 0x7fffffff;
	private int[] mt = new int[N];
	private int mti = N + 1;
	
	public void init_genrand(int s) {
		mt[0] = s & 0xffffffff;
		for (mti = 1; mti < N; mti++) {
			int temp = (1812433253 * (mt[mti - 1] ^ (mt[mti - 1] >>> 30))) & 0xFFFFFFFF;
			mt[mti] = temp + mti;
			mt[mti] &= 0xffffffff;
		}
	}
	
	public void init_by_array(int[] init_key, int key_length) {
		int i, j, k;
		init_genrand(19650218);
		i = 1;
		j = 0;
		k = (N > key_length ? N : key_length);
		for (; k != 0; k--) {
			mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >>> 30)) * 1664525)) + init_key[j] + j;
			mt[i] &= 0xffffffff;
			i++; 
			j++;
			if (i >= N) { 
				mt[0] = mt[N - 1]; 
				i = 1; 
			}
			if (j >= key_length) {
				j = 0;
			}
		}
		for (k = N - 1; k != 0; k--) {
			mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >>> 30)) * 1566083941)) - i;
			mt[i] &= 0xffffffff;
			i++;
			if (i >= N) { 
				mt[0] = mt[N - 1];
				i = 1; 
			}
		}
		mt[0] = 0x80000000;
	}
	
	public long genrand_int32() {
		int y;
		int[] mag01 = {0x0, MATRIX_A};
		if (mti >= N) {
			int kk;	
			if (mti == N + 1) {
				init_genrand(5489);
			}
			for (kk = 0; kk < N - M; kk++) {
				y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
				mt[kk] = mt[kk + M] ^ (y >>> 1) ^ mag01[y & 0x1];
			}
			for (; kk < N - 1; kk++) {
				y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
				mt[kk] = mt[kk + (M - N)] ^ (y >>> 1) ^ mag01[y & 0x1];
			}
			y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
			mt[N - 1] = mt[M - 1] ^ (y >>> 1) ^ mag01[y & 0x1];
			mti = 0;
		}
		y = mt[mti++];
		y ^= (y >>> 11);
		y ^= (y << 7) & 0x9d2c5680;
		y ^= (y << 15) & 0xefc60000;
		y ^= (y >>> 18);
		return y & 0xffffffffL;
	}
	
	public int genrand_int31() {
		return (int)(genrand_int32() >> 1);
	}
	
	public double genrand_real1() {
		return genrand_int32() * (1.0 / 4294967295.0); 
	}
	
	public double genrand_real2() {
		return genrand_int32() * (1.0 / 4294967296.0);
	}
	
	public double genrand_real3() {
		return ((double)(genrand_int32()) + 0.5) * (1.0 / 4294967296.0);
	}
	
	public double genrand_res53() { 
		long a = genrand_int32() >>> 5, b = genrand_int32() >>> 6;
		return(a * 67108864.0 + b) * (1.0 / 9007199254740992.0);
	}
	
	public MersenneTwisterRandom() {
		
	}
	
    public int nextInt(int min, int max) {
        return min + (int)Math.floor(genrand_real2() * (max - min + 1));
    }
	
	public static final void main(String[] args) {
		{
			String strTrace = "";
			int i;
			int[] init = {0x123, 0x234, 0x345, 0x456};
			MersenneTwisterRandom random = new MersenneTwisterRandom();
			random.init_by_array(init, init.length);
			strTrace += "1000 outputs of genrand_int32()\n";
			for (i = 0; i < 1000; i++) {
				strTrace += random.genrand_int32() + " ";
				if (i % 5 == 4) {
					strTrace += "\n";
				}
			}
			strTrace += "\n1000 outputs of genrand_real2()\n";
			for (i = 0; i < 1000; i++) {
				strTrace += random.genrand_real2() + " ";
				if (i % 5 == 4) 
				{
					strTrace += "\n";
				}
			}
			System.out.println(strTrace);
		}
		{
			//coin test
			MersenneTwisterRandom mt = new MersenneTwisterRandom();
			mt.init_genrand((int)System.currentTimeMillis());
			int heads = 0;
			int tails = 0;
			for (int j = 1; j <= 1000000; j++) {
				int i = (int)Math.floor(mt.genrand_real2() * 2);
				if (i == 0) { 
					heads ++;
				} else { 
					tails ++;
				}
			}
			System.out.println("heads = " + heads);
			System.out.println("tails = " + tails);
		}
	}
}

 

注意，我不能保证它的运行结果是正确的。

通常我喜欢像这样取一个整数范围内的随机整数：

 

		MersenneTwisterRandom mt = new MersenneTwisterRandom();
		mt.init_genrand((int)System.currentTimeMillis());
		int total = getCount(context);
		int id = mt.nextInt(0, total - 1);