# 这是一个“足够好”的随机algorithm; 为什么不使用，如果它更快？

` `public class QuickRandom { private double prevNum; private double magicNumber; public QuickRandom(double seed1, double seed2) { if (seed1 >= 1 || seed1 < 0) throw new IllegalArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1); prevNum = seed1; if (seed2 <= 1 || seed2 > 10) throw new IllegalArgumentException("Seed 2 must be > 1 and <= 10, not " + seed2); magicNumber = seed2; } public QuickRandom() { this(Math.random(), Math.random() * 10); } public double random() { return prevNum = (prevNum*magicNumber)%1; } }` `

` `public static void main(String[] args) { QuickRandom qr = new QuickRandom(); /*for (int i = 0; i < 20; i ++) { System.out.println(qr.random()); }*/ //Warm up for (int i = 0; i < 10000000; i ++) { Math.random(); qr.random(); System.nanoTime(); } long oldTime; oldTime = System.nanoTime(); for (int i = 0; i < 100000000; i ++) { Math.random(); } System.out.println(System.nanoTime() - oldTime); oldTime = System.nanoTime(); for (int i = 0; i < 100000000; i ++) { qr.random(); } System.out.println(System.nanoTime() - oldTime); }` `

` `0.612201846732229 0.5823974655091941 0.31062451498865684 0.8324473610354004 0.5907187526770246 0.38650264675748947 0.5243464344127049 0.7812828761272188 0.12417247811074805 0.1322738256858378 0.20614642573072284 0.8797579436677381 0.022122999476108518 0.2017298328387873 0.8394849894162446 0.6548917685640614 0.971667953190428 0.8602096647696964 0.8438709031160894 0.694884972852229` `

` `5456313909 1427223941` `

• 我的algorithm是否“足够好”（比如说，一个真正的随机数字不是太重要的游戏）？
• 为什么`Math.random`这么做似乎只是简单的乘法和切除小数就足够了？

` `package com.stackoverflow.q14491966; import java.util.Arrays; public class Test { public static void main(String[] args) throws Exception { QuickRandom qr = new QuickRandom(); int[] frequencies = new int[10]; for (int i = 0; i < 100000; i++) { frequencies[(int) (qr.random() * 10)]++; } printDistribution("QR", frequencies); frequencies = new int[10]; for (int i = 0; i < 100000; i++) { frequencies[(int) (Math.random() * 10)]++; } printDistribution("MR", frequencies); } public static void printDistribution(String name, int[] frequencies) { System.out.printf("%n%s distribution |8000 |9000 |10000 |11000 |12000%n", name); for (int i = 0; i < 10; i++) { char[] bar = " ".toCharArray(); // 50 chars. Arrays.fill(bar, 0, Math.max(0, Math.min(50, frequencies[i] / 100 - 80)), '#'); System.out.printf("0.%dxxx: %6d :%s%n", i, frequencies[i], new String(bar)); } } }` `

` `QR distribution |8000 |9000 |10000 |11000 |12000 0.0xxx: 11376 :################################# 0.1xxx: 11178 :############################### 0.2xxx: 11312 :################################# 0.3xxx: 10809 :############################ 0.4xxx: 10242 :###################### 0.5xxx: 8860 :######## 0.6xxx: 9004 :########## 0.7xxx: 8987 :######### 0.8xxx: 9075 :########## 0.9xxx: 9157 :########### MR distribution |8000 |9000 |10000 |11000 |12000 0.0xxx: 10097 :#################### 0.1xxx: 9901 :################### 0.2xxx: 10018 :#################### 0.3xxx: 9956 :################### 0.4xxx: 9974 :################### 0.5xxx: 10007 :#################### 0.6xxx: 10136 :##################### 0.7xxx: 9937 :################### 0.8xxx: 10029 :#################### 0.9xxx: 9945 :###################` `

` `QR distribution |8000 |9000 |10000 |11000 |12000 0.0xxx: 41788 :################################################## 0.1xxx: 17495 :################################################## 0.2xxx: 10285 :###################### 0.3xxx: 7273 : 0.4xxx: 5643 : 0.5xxx: 4608 : 0.6xxx: 3907 : 0.7xxx: 3350 : 0.8xxx: 2999 : 0.9xxx: 2652 :` `

• 从种子价值和乘数开始。
• 要生成一个随机数字：
• 乘数乘以种子。
• 设置种子等于这个值。
• 返回这个值。

` `0.10 -> 0.20` `

` `0.09 -> 0.18 0.11 -> 0.22` `

# 代码

` `using System; using System.Drawing; using System.Drawing.Imaging; namespace QuickRandomTest { public class QuickRandom { private double prevNum; private readonly double magicNumber; private static readonly Random rand = new Random(); public QuickRandom(double seed1, double seed2) { if (seed1 >= 1 || seed1 < 0) throw new ArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1); prevNum = seed1; if (seed2 <= 1 || seed2 > 10) throw new ArgumentException("Seed 2 must be > 1 and <= 10, not " + seed2); magicNumber = seed2; } public QuickRandom() : this(rand.NextDouble(), rand.NextDouble() * 10) { } public double Random() { return prevNum = (prevNum * magicNumber) % 1; } } class Program { static void Main(string[] args) { var rand = new Random(); var qrand = new QuickRandom(); int w = 600; int h = 600; CreateMatrix(w, h, rand.NextDouble).Save("System.Random.png", ImageFormat.Png); CreateMatrix(w, h, qrand.Random).Save("QuickRandom.png", ImageFormat.Png); } private static Image CreateMatrix(int width, int height, Func<double> f) { var bitmap = new Bitmap(width, height); for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { var c = (int) (f()*255); bitmap.SetPixel(x, y, Color.FromArgb(c,c,c)); } } return bitmap; } } }` `

（顺便说一句，好的谚语是：最快的代码是不运行的代码，你可以在世界上做最快的随机（），但是如果它不是非常随机的话就不好）

1. 将输出转换为char值
2. 将字符值写入文件
3. 压缩文件

` `import java.io.*; public class QuickRandom { private double prevNum; private double magicNumber; public QuickRandom(double seed1, double seed2) { if (seed1 >= 1 || seed1 < 0) throw new IllegalArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1); prevNum = seed1; if (seed2 <= 1 || seed2 > 10) throw new IllegalArgumentException("Seed 2 must be > 1 and <= 10, not " + seed2); magicNumber = seed2; } public QuickRandom() { this(Math.random(), Math.random() * 10); } public double random() { return prevNum = (prevNum*magicNumber)%1; } public static void main(String[] args) throws Exception { QuickRandom qr = new QuickRandom(); FileOutputStream fout = new FileOutputStream("qr20M.bin"); for (int i = 0; i < 20000000; i ++) { fout.write((char)(qr.random()*256)); } } }` `

` `Cris-Mac-Book-2:rt cris\$ zip -9 qr20M.zip qr20M.bin2 adding: qr20M.bin2 (deflated 16%) Cris-Mac-Book-2:rt cris\$ ls -al total 104400 drwxr-xr-x 8 cris staff 272 Jan 25 05:09 . drwxr-xr-x+ 48 cris staff 1632 Jan 25 05:04 .. -rw-r--r-- 1 cris staff 1243 Jan 25 04:54 QuickRandom.class -rw-r--r-- 1 cris staff 883 Jan 25 05:04 QuickRandom.java -rw-r--r-- 1 cris staff 16717260 Jan 25 04:55 qr20M.bin.gz -rw-r--r-- 1 cris staff 20000000 Jan 25 05:07 qr20M.bin2 -rw-r--r-- 1 cris staff 16717402 Jan 25 05:09 qr20M.zip` `

XD除了开玩笑之外，除了这里所说的一切外，我想引用testing随机序列“是一个艰巨的任务”[1]，并且有几个testing检查伪随机数的某些属性，你可以find很多在这里： http : //www.random.org/analysis/#2005

` `static double chisquare(int numberCount, int maxRandomNumber) { long[] f = new long[maxRandomNumber]; for (long i = 0; i < numberCount; i++) { f[randomint(maxRandomNumber)]++; } long t = 0; for (int i = 0; i < maxRandomNumber; i++) { t += f[i] * f[i]; } return (((double) maxRandomNumber * t) / numberCount) - (double) (numberCount); }` `

χ²检验的思想是检查产生的数字是否合理分布。 如果我们生成N个小于r的正数，那么我们期望得到每个数值的N / r个数。 但是—这是事情的本质—所有价值的发生频率不应该是完全一样的：那不会是随机的！

` `abstract class RandomFunction { public abstract int randomint(int range); } public class test { static QuickRandom qr = new QuickRandom(); static double chisquare(int numberCount, int maxRandomNumber, RandomFunction function) { long[] f = new long[maxRandomNumber]; for (long i = 0; i < numberCount; i++) { f[function.randomint(maxRandomNumber)]++; } long t = 0; for (int i = 0; i < maxRandomNumber; i++) { t += f[i] * f[i]; } return (((double) maxRandomNumber * t) / numberCount) - (double) (numberCount); } public static void main(String[] args) { final int ITERATION_COUNT = 1000; final int N = 5000000; final int R = 100000; double total = 0.0; RandomFunction qrRandomInt = new RandomFunction() { @Override public int randomint(int range) { return (int) (qr.random() * range); } }; for (int i = 0; i < ITERATION_COUNT; i++) { total += chisquare(N, R, qrRandomInt); } System.out.printf("Ave Chi2 for QR: %f \n", total / ITERATION_COUNT); total = 0.0; RandomFunction mathRandomInt = new RandomFunction() { @Override public int randomint(int range) { return (int) (Math.random() * range); } }; for (int i = 0; i < ITERATION_COUNT; i++) { total += chisquare(N, R, mathRandomInt); } System.out.printf("Ave Chi2 for Math.random: %f \n", total / ITERATION_COUNT); } }` `

` `Ave Chi2 for QR: 108965,078640 Ave Chi2 for Math.random: 99988,629040` `

[1] SEDGEWICK ROBERT， Calgorithm ，Addinson Wesley Publishing Company，1990，第516-518页

Period是PRNG开始重复之前的序列长度。 只要PRNG机器进行状态转换到与过去状态相同的状态，就会发生这种情况。 从那里，它将重复在该州开始的过渡。 PRNG的另一个问题可能是less数独特的序列，以及重复的特定序列上的简并收敛。 也可能有不希望的模式。 例如，假设PRNG在十进制数字打印时看起来是相当随机的，但通过检查二进制数值可以看出，在每次调用时，位4只是在0和1之间切换。 哎呀！

` `public class QuickRandom { private long seed; private static final long MULTIPLIER = 0x5DEECE66DL; private static final long ADDEND = 0xBL; private static final long MASK = (1L << 48) - 1; public QuickRandom() { this((8682522807148012L * 181783497276652981L) ^ System.nanoTime()); } public QuickRandom(long seed) { this.seed = (seed ^ MULTIPLIER) & MASK; } public double nextDouble() { return (((long)(next(26)) << 27) + next(27)) / (double)(1L << 53); } private int next(int bits) { seed = (seed * MULTIPLIER + ADDEND) & MASK; return (int)(seed >>> (48 - bits)); } }` `

` `Random random = ThreadLocalRandom.current();` `

'Random' is more than just about getting numbers…. what you have is pseudo-random

If pseudo-random is good enough for your purposes, then sure, it's way faster (and XOR+Bitshift will be faster than what you have)

Rolf

OK, after being too hasty in this answer, let me answer the real reason why your code is faster:

This method is properly synchronized to allow correct use by more than one thread. However, if many threads need to generate pseudorandom numbers at a great rate, it may reduce contention for each thread to have its own pseudorandom-number generator.

This is likely why your code is faster.

java.util.Random is not much different, a basic LCG described by Knuth. However it has main 2 main advantages/differences:

• thread safe – each update is a CAS which is more expensive than a simple write and needs a branch (even if perfectly predicted single threaded). Depending on the CPU it could be significant difference.
• undisclosed internal state – this is very important for anything non-trivial. You wish the random numbers not to be predictable.

Below it's the main routine generating 'random' integers in java.util.Random.

` `protected int next(int bits) { long oldseed, nextseed; AtomicLong seed = this.seed; do { oldseed = seed.get(); nextseed = (oldseed * multiplier + addend) & mask; } while (!seed.compareAndSet(oldseed, nextseed)); return (int)(nextseed >>> (48 - bits)); }` `

If you remove the AtomicLong and the undisclosed sate (ie using all bits of the `long` ), you'd get more performance than the double multiplication/modulo.

Last note: `Math.random` should not be used for anything but simple tests, it's prone to contention and if you have even a couple of threads calling it concurrently the performance degrades. One little known historical feature of it is the introduction of CAS in java – to beat an infamous benchmark (first by IBM via intrinsics and then Sun made "CAS from Java")

This is the random function I use for my games. It's pretty fast, and has good (enough) distribution.

` `public class FastRandom { public static int randSeed; public static final int random() { // this makes a 'nod' to being potentially called from multiple threads int seed = randSeed; seed *= 1103515245; seed += 12345; randSeed = seed; return seed; } public static final int random(int range) { return ((random()>>>15) * range) >>> 17; } public static final boolean randomBoolean() { return random() > 0; } public static final float randomFloat() { return (random()>>>8) * (1.f/(1<<24)); } public static final double randomDouble() { return (random()>>>8) * (1.0/(1<<24)); } }` `