Configuring the XORShift Generator to Return a Number Within the Maximum

Question

I need to generate random integers within the maximum. Since performance is important, I decided to use the XORShift generator instead of the Java Random class.

long seed = System.nanoTime(); seed ^= (seed << 21); seed ^= (seed >>> 35); seed ^= (seed << 4); 

This implementation _(source) gives me a long integer, but I really want an integer from 0 and maximum.

 public int random(int max){ /*...*/} 

What is the most efficient way to implement this method?

Answer 1

I liked it with your code and came up with the following:

 public class XORShiftRandom { private long last; public XORShiftRandom() { this(System.currentTimeMillis()); } public XORShiftRandom(long seed) { this.last = seed; } public int nextInt(int max) { last ^= (last << 21); last ^= (last >>> 35); last ^= (last << 4); int out = (int) last % max; return (out < 0) ? -out : out; } } 

I did a simple test and it is about Four times faster than java.util.Random

If you are interested in how this works, you can read this paper :

Legal information:

The above code is for research use only and not for replacement to a random case or SecureRandom.

Answer 2

Sowing

There are a lot of problems. If you use nanoTime more than once, you will definitely do it wrong, because nanoTime is slow (hundreds of nanoseconds). Moreover, this leads to poor quality.

So, let's say you sow your generator only once.

Uniformity

If you care about uniformity, then there are at least two problems:

Xorshift

It never generates zero (unless you are lucky with sowing, and then zero is all you ever get).

It is easily solvable with something as simple as

 private long nextLong() { x ^= x << 21; x ^= x >>> 35; x ^= x << 4; y += 123456789123456789L; return x + y; } 

The constant used is fairly arbitrary, except that it must be odd. For best results, it should be large (so that all bits change frequently), it should have many bit transitions (occurrences 10 and 01 in binary representation), and it should not be too regular ( 0x55...55 bad).

However, with x!=0 and any odd constant, uniformity and period of the generator 2**64 * (2*64-1) guaranteed.

I would suggest sowing, for example

 seed = System.nanoTime(); x = seed | 1; y = seed; 

nextInt (int limit)

The accepted answer provides unevenly distributed values ​​for the reason that I mentioned in comment . Whether this is correct is a bit complicated, you can copy the code from Random#nextInt , or you can try something like this (untested):

 public int nextInt(int limit) { checkArgument(limit > 0); int mask = -1 >>> Integer.numberOfLeadingZeros(limit); while (true) { int result = (int) nextLong() & mask; if (result < limit) return result; } } 

Above, mask looks binary, like 0...01...1 , where the highest corresponds to the highest of limit . Using it, a uniformly distributed number is obtained in the range 0..mask (uniformity is easy, since mask+1 is a power of two). Conditional deviation of numbers not lower than limit . Like limit > mask/2 , this happens with a probability below 50%, and therefore the expected number of iterations is below 2.

Recommendation

Cheating is fun, but testing is difficult, and I would recommend using ThreadLocalRandom instead if you don't need reproducibility.