Adjusting XORShift generator to return a number within a maximum

Question

I need to generate random integers within a maximum. Since performance is critical, I decided to use a XORShift generator instead of Java's Random class.

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

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

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

What it is the most efficient way to implement this method?

Answer 1

I had some fun with your code and came up with this:

public class XORShiftRandom {

private long last;
private long inc;

public XORShiftRandom() {
    this(System.currentTimeMillis());
}

public XORShiftRandom(long seed) {
    this.last = seed | 1;
    inc = seed;
}

public int nextInt(int max) {
    last ^= (last << 21);
    last ^= (last >>> 35);
    last ^= (last << 4);
    inc += 123456789123456789L;
    int out = (int) ((last+inc) % max);     
    return (out < 0) ? -out : out;
}

}

I did a simple test and it is about Four times as fast as the java.util.Random

If you are intrested in how it works you can read this paper:

Disclamer:

The code above is designed to be used for research only, and not as a replacement to the stock Random or SecureRandom.

Answer 2

Seeding

There are many problems here. In case, you're using nanoTime more than once, you'd definitely doing it wrong as nanoTime is slow (hundreds of nanoseconds). Moreover, doing this probably leads to bad quality.

So let's assume, you seed your generator just once.

Uniformity

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

Xorshift

It never generates zero (unless you unlucky with seeding and then zero is all you ever get).

This is easily solvable by something as simple as

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

The used constant is pretty arbitrary, except for it must be odd. For best results, it should be big (so that all bits change often), it should have many bit transitions (occurrences of 10 and 01 in the binary representation) and it shouldn't be too regular (0x55...55 is bad).

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

I'd suggest seeding like

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

nextInt(int limit)

The accepted answer provides non-uniformly distributed values for the reason I mentioned in a comment. Doing it right 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, the mask looks in binary like 0...01...1, where the highest one corresponds with the highest one of limit. Using it, a uniformly distributed number in the range 0..mask gets produced (unifomrnity is easy as mask+1 is a power of two). The conditional refuses numbers not below limit. As limit > mask/2, this happens with a probability below 50%, and therefore the expected number of iterations is below 2.

Recommendation

Fooling around with this is fun, but testing it is hard and I'd recommend using ThreadLocalRandom instead, unless you need reproducibility.