On 10/04/2019 13:46, Alex Herbert wrote:
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 bits. So this is effectively just a left shift followed by a
right shift to discard significant bits from the number. The same
result can be achieved using a mask to discard the 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.
I suggest updating the methods to use masking. Note that the output
from the following method will be the same:
Update: It will not be the same as this method returns the lower order
bits, not the higher order bits. See below.
public int nextInt(int n) {
checkStrictlyPositive(n);
final int nm1 = n - 1;
if ((n & nm1) == 0) {
// Range is a power of 2
return (nextInt() >>> 1) & nm1;
}
int bits;
int val;
do {
bits = nextInt() >>> 1;
val = bits % n;
} while (bits - val + nm1 < 0);
return val;
}
It can be sped up by removing the unsigned shift for the power of 2
case, but that would make the output change as the least significant
bit is now part of the result.
Note:
The current method originates from the implementation in
java.util.Random. There the Javadoc states:
"The algorithm treats the case where n is a power of two specially: it
returns the correct number of high-order bits from the underlying
pseudo-random number generator. In the absence of special treatment, the
correct number of low-order bits would be returned. Linear congruential
pseudo-random number generators such as the one implemented by this
class are known to have short periods in the sequence of values of their
low-order bits. Thus, this special case greatly increases the length of
the sequence of values returned by successive calls to this method if n
is a small power of two."
java.util.Random does not support nextLong(long).
So the change to the implementation would require that the underlying
generator is a good provider of lower order bits. This is assumed to be
the case for ThreadLocalRandom which is why the implementation is
different. The same faster method is also used in SplittableRandom.
Given that the generators in Commons RNG are mostly good providers of
bits the change to use the lower order bits should be reasonable.
Alex
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
