探索各种随机函数 ( Java 环境 )

其实写这篇文章的原由是最近准备在Java上写一个Perlin噪声的插件,所以对各种噪声函数有了一丢丢的了解,若有问题还请大家指正。转载的话希望能注明出处。

注意,本教程中的随机函数均是形参为整形,返回值为区间[0,1)内的单精浮点数的函数。测试均为1~10000的随机数生成速度测试(1D – 输入x、2D – 输入x, y)。

更新记录

2016.1.22 – 初稿。

2016.1.28

(1) – 更新了Wichman-Hill随机数的算法,修改内容。增加了几个随机算法。

(2) – 统计出了各个方法比较后的分数。

随机方法

1.Wichman-Hill 随机数产生器

Excel的随机函数曾用的方法,参考文献:

  • Wichman, B.A. 和 I.D. Hill,Algorithm AS 183:An Efficient and Portable Pseudo-Random Number Generator,《Applied Statistics》,31,188-190,1982。
  • Wichman, B.A. 和 I.D. Hill,Building a Random-Number Generator,BYTE,第127-128 页,1987 年 3 月。
  • Rotz, W. 和 E. Falk,D. Wood 和 J. Mulrow,A Comparison of Random Number Generators Used in Business,发表于 2001 年在佐治亚州亚特兰大市举行的“统计学联合会议”上。

直接上源码(2D请前去Github上查看):

/**
 * This is a method of Wichman-Hill random number generator.
 * 
 * @param x
 * A seed for generator.
 * @return A float random value between [0.0,1.0)
 */
public static float randomWH(java.lang.Integer x) {
   int[] seed = new int[3];
   seed[0] = (171 * x) % 30269;
   seed[1] = (172 * (30000 – x)) % 30307;
   seed[2] = (170 * x) % 30323;
   return (x / Math.abs(x)) 
           * (seed[0] / 30269.0F + seed[1] / 30307.0F + seed[2] / 30323.0F) % 1.0F; 
}

以下是测试结果:

Start testing randomWH(), test: Generate 10000 numbers(1D).
Testing randomWH() completed, using time: 10 ms.

Start testing randomWH(), test: Generate 10000 numbers(2D).
Testing randomWH() completed, using time: 7 ms.

还蛮乐观,但是图像就…

无论怎么改,还是呈现了线性的趋势,波动很小……Orz

2.RSA 随机数产生器

RSA公钥算法大家都不会不熟悉吧,公认很靠谱的密钥算法。这里就是用了RSA的随机算法。参考:

  • Wikipedia – RSA problem

其公式:C = (x * exp P) mod N(P是质数,N是两个质数之积)

这是Java代码:

/**
 * This is a method of RSA.
 * 
 * @param x
 *            A seed for generator.
 * @return A float random value between [0.0,1.0)
 */
public static float randomRSA(java.lang.Integer x) {
	return (float) (x * Math.exp(seedRSA[0]) % seedRSA[1] / seedRSA[1]);
}

测试结果:

Start testing randomRSA(), test: Generate 10000 numbers(1D).
Testing randomRSA() completed, using time: 10 ms.

Start testing randomRSA(), test: Generate 10000 numbers(2D).
Testing randomRSA() completed, using time: 9 ms.

从图像看出,这个算法的随机性很赞。况且运算速度也不赖,适合使用。

3.Java 随机数产生器

Java自带的随机数(就是java.util.Random类),用过的都知道吧。那就直接上代码:

/**
 * This is a method of Java random number generator.
 * 
 * @param x
 *            A seed for generator.
 * @return A float random value between [0.0,1.0)
 */
public static float randomJava(java.lang.Integer x) {
	return (float) (new java.util.Random(1000 * x).nextDouble()); //乘1000来让种子间差距增大
}

这是测试数据:

Start testing randomJava(), test: Generate 10000 numbers(1D).
Testing randomJava() completed, using time: 11 ms.

Start testing randomJava(), test: Generate 10000 numbers(2D).
Testing randomJava() completed, using time: 8 ms.

非常优秀的随机数算法,速度快而且基本看不出规律。

4.简单的随机数产生器

又是扫荡Google的战利品,很抱歉忘记出处惹……代码:

/**
 * This is a method of basic random generator.
 * 
 * @param x
 *            A seed for generator.
 * @return A float random value between [0.0,1.0)
 */
public static float randomBasic(java.lang.Integer x) {
	x = (x << 13) ^ x;
	return (float) Math
		.abs((1.0 - ((x * (x * x * 15731 + 789221) + 1376312589) & 0x7fffffff) / 1073741824.0));
}

测试结果:

Start testing randomBasic(), test: Generate 10000 numbers(1D).
Testing randomBasic() completed, using time: 9 ms.

Start testing randomBasic(), test: Generate 10000 numbers(2D).
Testing randomBasic() completed, using time: 8 ms.

也是非常优秀的算法,随机的效果很棒,且用时也不长。

5.dotNet 随机数产生器

写了尼玛整整一个类啊我擦,不过是源码转写进来的,也没费什么力气。代码:

(DotNetRandom 类)

package kaaass.perlin2d.random;

/**
 * This is a random generator which translated from dotNet.
 * 
 * @author dotNet, KAAAsS(Translate)
 *
 */
class DotNetRandom {
	private final static int MBIG = Integer.MAX_VALUE;
	private final static int MSEED = 161803398;

	private int inext, inextp;
	private int[] SeedArray = new int[56];

	public DotNetRandom() {
		this((int) System.currentTimeMillis());
	}

	public DotNetRandom(int Seed) {
		int ii;
		int mj, mk;

		mj = MSEED - Math.abs(Seed);
		SeedArray[55] = mj;
		mk = 1;
		for (int i = 1; i < 55; i++) {
			/*
			 * Apparently the range [1..55] is special (Knuth) and so we're
			 * wasting the 0'th position.
			 */
			ii = (21 * i) % 55;
			SeedArray[ii] = mk;
			mk = mj - mk;
			if (mk < 0)
				mk += MBIG;
			mj = SeedArray[ii];
		}
		for (int k = 1; k < 5; k++) {
			for (int i = 1; i < 56; i++) {
				SeedArray[i] -= SeedArray[1 + (i + 30) % 55];
				if (SeedArray[i] < 0) SeedArray[i] += MBIG; } } inext = 0; inextp = 21; Seed = 1; } /** * Return a new random number [0,1) and reSeed the Seed array. * @return A double [0,1) */ protected double rand() { int retVal; int locINext = inext; int locINextp = inextp; if (++locINext >= 56)
			locINext = 1;
		if (++locINextp >= 56)
			locINextp = 1;
		retVal = SeedArray[locINext] - SeedArray[locINextp];
		if (retVal < 0)
			retVal += MBIG;
		SeedArray[locINext] = retVal;
		inext = locINext;
		inextp = locINextp;
		/*
		 * Including this division at the end gives us significantly improved
		 * random number distribution.
		 */
		return (retVal * (1.0 / MBIG));
	}

}

(调用)

/**
 * This is a method of doNet random number generator.
 * 
 * @param x
 *            A seed for generator.
 * @return A float random value between [0.0,1.0)
 */
public static float randomDoNet(java.lang.Integer x) {
	return (float) new DotNetRandom(1000 * x).rand();
}

测试:

Start testing randomDoNet(), test: Generate 10000 numbers(1D).
Testing randomDoNet() completed, using time: 61 ms.

Start testing randomDoNet(), test: Generate 10000 numbers(2D).
Testing randomDoNet() completed, using time: 109 ms.

目瞪口呆这速度,这质量……是我的锅吗……

统计

经过比对之后,终于得到了大致的评分表(已按高低名次排序):

看来Java的综合实力不差。同样可以在图表中看到实际上Basic的效率是最好的,然而与Java的差距也只有1毫秒。但是Java的质量要好上不少。RSA质量不错,基本和Basic持平,但是速度上还是差了一丢丢。

这里是对比方法:

  • 速度:1-D、2-D随机数生成速度排序(上图表格中给出的是ms成绩),打出得分:1~5(各占20%)
  • 随机程度:通过方差以及其他统计分析得出,打出得分:1~5(最好~最差)(占40%)
  • 重复率:通过对插值图像的分析得出,打出得分:1~5(最好~最差)(占20%)
  • 结果按百分制处理后,求出与100的差为最终成绩

当然本对比可能不是严谨科学,仅供参考。

附测试代码:

public static void testRandom(String method) {
	RandomGenerator obj = new RandomGenerator();
	Method m;
	try {
		long t;
		// 1-D tests
		m = RandomGenerator.class.getMethod(method, Integer.class);
		t = System.currentTimeMillis();
		System.out.println("Start testing " + method
				+ "(), test: Generate 10000 numbers(1D).");
		for (int i = 1; i <= 10000; i++) {
			m.invoke(obj, i);
		}
		System.out.println("Testing " + method
				+ "() completed, using time: "
				+ (System.currentTimeMillis() - t) + " ms.\n");
		// 2-D tests
		m = RandomGenerator.class.getMethod(method, Integer.class,
				Integer.class);
		t = System.currentTimeMillis();
		System.out.println("Start testing " + method
				+ "(), test: Generate 10000 numbers(2D).");
		for (int i = 1; i <= 100; i++) {
			for (int ii = 1; ii <= 100; ii++) {
				m.invoke(obj, i, ii);
			}
		}
		System.out.println("Testing " + method
				+ "() completed, using time: "
				+ (System.currentTimeMillis() - t) + " ms.\n");
		// Generate data
		m = RandomGenerator.class.getMethod(method, Integer.class);
		String s1 = "";
		String s2 = "";
		for (int i = 1; i <= 50; i++) {
			if (s1.equals("")) {
				s1 = String.valueOf(i);
			} else {
				s1 = s1 + "," + String.valueOf(i);
			}
			if (s2.equals("")) {
				s2 = "" + (float) m.invoke(obj, i);
			} else {
				s2 = s2 + "," + (float) m.invoke(obj, i);
			}
		}
		System.out.println(s1);
		System.out.println(s2);
	} catch (NoSuchMethodException | SecurityException e) {
		e.printStackTrace();
		return;
	} catch (IllegalAccessException e) {
		// TODO 自动生成的 catch 块
		e.printStackTrace();
	} catch (IllegalArgumentException e) {
		// TODO 自动生成的 catch 块
		e.printStackTrace();
	} catch (InvocationTargetException e) {
		// TODO 自动生成的 catch 块
		e.printStackTrace();
	}
}

详情请看我的Github



相关文章

发表评论

Comment form

(*) 表示必填项

还没有评论。

跳到底部
返回顶部