[jira] [Commented] (RNG-90) Improve nextInt(int) and nextLong(long) for powers of 2

["Alex D Herbert (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/RNG-90?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16886553#comment-16886553 ] 

Alex D Herbert commented on RNG-90:
-----------------------------------

This multiply method with rejection has been documented by Danial Lamire:

[Fast Random Integer Generation in an Interval|https://arxiv.org/abs/1805.10941]

It provides an algorithm that dynamically precomputes the {{fence}} value {{t}} using modulus only if the sample is likely to be rejected. Here is a prototype for a Java version allowing for the signed 32-bit arithmetic by conversion to long. The original c code is for unsigned 32-bit integers.
{code:java}
// Algorithm 5
public int nextInt(UniformRandomProvider rng, int s) {
    // s is assumed to be a positive int in the range [1, 2^31).
    long m = rng.nextInt() * (long) s;
    long l = m & 0xffffffffL;
    if (l < s) {
        // (2^32 - n) % n
        final long t = -s % s;
        while (l < t) {
            m = rng.nextInt() * (long) s;
            l = m & 0xffffffffL;
        }
    }
    return (int) (m >>> 32);
}
{code}

An alternative may be possible using only {{int}} variables by performing unsigned comparisons as per JDK 8 Integer.compareUnsigned by adding 0x80000000 to each value. This should also be investigated.


> 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
>            Priority: Minor
>          Time Spent: 50m
>  Remaining Estimate: 0h
>
> 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 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 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.14#76016)