commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Alex D Herbert (JIRA)" <j...@apache.org>
Subject [jira] [Created] (RNG-90) Improve nextInt(int) and nextLong(long) for powers of 2
Date Thu, 11 Apr 2019 12:47:00 GMT
Alex D Herbert created RNG-90:
---------------------------------

             Summary: Improve nextInt(int) and nextLong(long) for powers of 2
                 Key: RNG-90
                 URL: https://issues.apache.org/jira/browse/RNG-90
             Project: Commons RNG
          Issue Type: Improvement
          Components: core
    Affects Versions: 1.3
            Reporter: Alex D Herbert
            Assignee: Alex D Herbert


The code for nextInt(int) checks the range number n is a power of two and if so it computes
a fast solution:
{code:java}
    return (int) ((n * (long) (nextInt() >>> 1)) >> 31); 
{code}
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:
{code:java}
    return nextInt() & (n-1)
{code}
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:
{code:java}
@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;
}
{code}
This will update all providers to use the new method. Then the JDK implementation can be changed
to override the default:
{code:java}
@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);
}
{code}
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:
{code:java}
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;
}
{code}
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.



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

Mime
View raw message