Alex D Herbert created RNG90:

Summary: Improve nextInt(int) and nextLong(long) for powers of 2
Key: RNG90
URL: https://issues.apache.org/jira/browse/RNG90
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() & (n1)
{code}
This works if n is a power of 2 as (n1) 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 nonmasking
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)
