[
https://issues.apache.org/jira/browse/RNG-90?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16820581#comment-16820581
]
Alex D Herbert commented on RNG-90:
-----------------------------------
I could not believe that this method was without flaws. The clue is here:
{noformat}
floor( n * [0,1) )
{noformat}
The floor function results in a bias when n does not exactly divide into the
range (either 2^32 or 2^64).
I had opened a PR with the modifications and all the unit tests passed. This is
because the bias is very low for certain values of n.
I will add more information when I have quantified the bias.
> 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.3#76005)
