[ https://issues.apache.org/jira/browse/RNG-90?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16886553#comment-16886553 ]
Alex D Herbert edited comment on RNG-90 at 7/17/19 8:32 PM: ------------------------------------------------------------ This multiply method with rejection has been documented by Daniel Lemire: [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() & 0xffffffffL) * s; long l = m & 0xffffffffL; if (l < s) { // 2^32 % s final long t = (1L << 32) % s; while (l < t) { m = (rng.nextInt() & 0xffffffffL) * s; l = m & 0xffffffffL; } } return (int) (m >>> 32); } {code} was (Author: alexherbert): This multiply method with rejection has been documented by Daniel Lemire: [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)