# commons-issues mailing list archives

##### Site index · List index
Message view
Top
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

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