[RNG-90] Improve nextInt(int) and nextLong(long) for powers of 2

• Type: Improvement
• Status: Closed
• Priority: Minor
• Resolution: Implemented
• Affects Version/s: 1.3
• Fix Version/s: 1.3
• Component/s: core
• Assignee: Alex Herbert
• Reporter: Alex Herbert
• Created: 11/Apr/19 12:46
• Updated: 11/Nov/19 14:25
• Resolved: 05/Aug/19 20:04

Description

The code for nextInt(int) checks the range number n is a power of two and if so it computes a fast solution:

    return (int) ((n * (long) (nextInt() >>> 1)) >> 31); 

This scales a 31 bit positive number by a power of 2 (i.e. n) then discards the least significant bits. An alternative result can be achieved using a mask to discard the most significant bits:

    return nextInt() & (n-1)

This works if n is a power of 2 as (n-1) will be all the bits set below it. Note: This method is employed by ThreadLocalRandom.

It also makes the method applicable to nextLong(long) since you no longer require the long multiplication arithmetic.

The mask version is applicable to any generator with a long period in the lower order bits. The current version for any generator with a short period in the lower order bits. The non-masking method is employed by java.util.Random which is a weak generator.

The methods are currently in BaseProvider. I suggest dividing the methods to use protected methods to compute the result:

@Override
public int nextInt(int n) {
    checkStrictlyPositive(n);
    final int nm1 = n - 1;
    if ((n & nm1) == 0) {
        // Range is a power of 2
        return nextIntPowerOfTwo(n, nm1);
    }
    return nextIntNonPowerOfTwo(n, nm1);
}

/**
 * Generates an {@code int} value between 0 (inclusive) and the
 * specified value (exclusive).
 *
 * @param n Bound on the random number to be returned. This is a power of 2.
 * @param nm1 The bound value minus 1.
 * @return a random {@code int} value between 0 (inclusive) and {@code n}
 * (exclusive).
 */
protected int nextIntPowerOfTwo(int n, int nm1) {
    return nextInt() & nm1;
}

/**
 * Generates an {@code int} value between 0 (inclusive) and the specified value
 * (exclusive).
 *
 * @param n Bound on the random number to be returned. This is not a power of 2.
 * @param nm1 The bound value minus 1.
 * @return a random {@code int} value between 0 (inclusive) and {@code n} (exclusive).
 */
protected int nextIntNonPowerOfTwo(int n, int nm1) {
    int bits;
    int val;
    do {
        bits = nextInt() >>> 1;
        val = bits % n;
    } while (bits - val + nm1 < 0);
    return val;
}

@Override
public long nextLong(long n) {
    checkStrictlyPositive(n);
    final long nm1 = n - 1;
    if ((n & nm1) == 0) {
        // Range is a power of 2
        return nextLongPowerOfTwo(n, nm1);
    }
    return nextLongNonPowerOfTwo(n, nm1);
}

/**
 * Generates an {@code long} value between 0 (inclusive) and the
 * specified value (exclusive).
 *
 * @param n Bound on the random number to be returned. This is a power of 2.
 * @param nm1 The bound value minus 1.
 * @return a random {@code long} value between 0 (inclusive) and {@code n}
 * (exclusive).
 */
protected long nextLongPowerOfTwo(long n, long nm1) {
    return nextLong() & nm1;
}

/**
 * Generates an {@code long} value between 0 (inclusive) and the specified value
 * (exclusive).
 *
 * @param n Bound on the random number to be returned. This is not a power of 2.
 * @param nm1 The bound value minus 1.
 * @return a random {@code long} value between 0 (inclusive) and {@code n} (exclusive).
 */
protected long nextLongNonPowerOfTwo(long n, long nm1) {
    long bits;
    long val;
    do {
        bits = nextLong() >>> 1;
        val = bits % n;
    } while (bits - val + nm1 < 0);
    return val;
}

This will update all providers to use the new method. Then the JDK implementation can be changed to override the default:

@Override
protected int nextIntPowerOfTwo(int n, int nm1) {
    return (int) ((n * (long) (nextInt() >>> 1)) >> 31);
}

@Override
protected long nextLongPowerOfTwo(long n, long nm1) {
    return nextLongNonPowerOfTwo(n, nm1);
}

I do not know how the use of protected methods will affect performance. An alternative is to inline the entire computation for the new masking method:

public int nextInt(int n) {
    checkStrictlyPositive(n);
    final int nm1 = n - 1;
    if ((n & nm1) == 0) {
        // Range is a power of 2
        return nextInt() & nm1;
    }
    int bits;
    int val;
    do {
        bits = nextInt() >>> 1;
        val = bits % n;
    } while (bits - val + nm1 < 0);
    return val;
}

Then rewrite the entire method in the JDK generator. This will be less flexible if other generators are added than have short periods in the lower order bits.

Issue Links

• relates to: RNG-95 DiscreteUniformSampler
• links to: GitHub Pull Request #38
• links to: GitHub Pull Request #60