[
https://issues.apache.org/jira/browse/RNG-172?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Alex Herbert resolved RNG-172.
------------------------------
Resolution: Implemented
Updated in commit:
994616fa38039c295535f24b5242bf0a7f5b0ead
> 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
> Priority: Trivial
> 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)
