Alex Herbert created RNG-172:
--------------------------------
Summary: UniformLongSampler can precompute the rejection limit
Key: RNG-172
URL: https://issues.apache.org/jira/browse/RNG-172
Project: Commons RNG
Issue Type: Improvement
Components: sampling
Affects Versions: 1.4
Reporter: Alex Herbert
Fix For: 1.5
The UniformLongSampler uses this rejection algorithm for non-powers of 2 range
'n':
{code:java}
@Override
public long sample() {
// Rejection algorithm copied from o.a.c.rng.core.BaseProvider
// to avoid the (n <= 0) conditional.
// See the JDK javadoc for java.util.Random.nextInt(int) for
// a description of the algorithm.
long bits;
long val;
do {
bits = rng.nextLong() >>> 1;
val = bits % n;
} while (bits - val + (n - 1) < 0);
return val;
}
{code}
This requires a modulus operation per iteration. Worst case expected iteration
of the loop is 2 times and thus 2 modulus calls.
However the statement {{while (bits - val + (n - 1) < 0)}} is checking if the
bits came from the range [0, limit) where limit is the largest multiple of n
that is a positive value. Essential the bits must uniformly be picked from a
range that can be used with modulus n and still be uniform for all values.
This limit can be precomputed and the sampling loop changed to have 1 modulus
call:
{code:java}
@Override
public long sample() {
// Note:
// This will have the same output as the rejection algorithm
// from o.a.c.rng.core.BaseProvider. The limit for the uniform
// positive value can be pre-computed. This ensures exactly
// 1 modulus operation per call.
long bits = rng.nextLong() >>> 1;
while (bits >= limit) {
bits = rng.nextLong() >>> 1;
}
return bits % n;
}
{code}
This does not work if the range n is a power of 2 as the limit is 2^63 and no
sample for bits can be above it. This sampler uses a different method for power
of 2 range and so the limit can be precomputed as used here.
The output from the sampler will be the same.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
