On 10/04/2019 15:59, Gilles Sadowski wrote:
Hello.

Le mer. 10 avr. 2019 à 15:22, Alex Herbert <alex.d.herb...@gmail.com> a écrit :
On 10/04/2019 13:46, Alex Herbert wrote:
The code for nextInt(int) checks the range number n is a power of two
and if so it computes a fast solution:

     return (int) ((n * (long) (nextInt() >>> 1)) >> 31);

This scales a 31 bit positive number by a power of 2 (i.e. n) then
discards bits. So this is effectively just a left shift followed by a
right shift to discard significant bits from the number. The same
result can be achieved using a mask to discard the significant bits:

     return nextInt() & (n-1)

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.

I suggest updating the methods to use masking. Note that the output
from the following method will be the same:
Update: It will not be the same as this method returns the lower order
bits, not the higher order bits. See below.
     public int nextInt(int n) {
         checkStrictlyPositive(n);

         final int nm1 = n - 1;
         if ((n & nm1) == 0) {
             // Range is a power of 2
             return (nextInt() >>> 1) & nm1;
         }
         int bits;
         int val;
         do {
             bits = nextInt() >>> 1;
             val = bits % n;
         } while (bits - val + nm1 < 0);

         return val;
     }

It can be sped up by removing the unsigned shift for the power of 2
case, but that would make the output change as the least significant
bit is now part of the result.


Note:

The current method originates from the implementation in
java.util.Random. There the Javadoc states:

"The algorithm treats the case where n is a power of two specially: it
returns the correct number of high-order bits from the underlying
pseudo-random number generator. In the absence of special treatment, the
correct number of low-order bits would be returned. Linear congruential
pseudo-random number generators such as the one implemented by this
class are known to have short periods in the sequence of values of their
low-order bits. Thus, this special case greatly increases the length of
the sequence of values returned by successive calls to this method if n
is a small power of two."

java.util.Random does not support nextLong(long).

So the change to the implementation would require that the underlying
generator is a good provider of lower order bits. This is assumed to be
the case for ThreadLocalRandom which is why the implementation is
different. The same faster method is also used in SplittableRandom.

Given that the generators in Commons RNG are mostly good providers
With the notable exception of "JDK"...

of bits the change to use the lower order bits should be reasonable.
... Hence, calling "nextInt(int)" on that provider will generate a
sequence even worse than it would be from direct calls to
"java.util.Random".

That's a dilemma.
Yes. The faster method will be OK for some but not all.

This method is in BaseProvider. So is used by all generators. The method and its alternative could be moved to NumberFactory (and tested to do what they say). Then any generator that shows poor results in BigCrush/Dieharder can be set to use the current implementation on the assumption that the lower order bits are poor. Any generator that is good can use the faster implementation via @Override.
Or conversely we can update so the default is the faster implementation 
and poor generators can override with the slower upper bits implementation.
So that would mean only the JDK overrides with its own method. Then 
other 'bad' generators can do this if they are added. Thoughts on this 
approach?
Since it's not recommended, and provided mainly as baseline for
showing that all the other implementations are better, we could
deprecate (but never delete) the "JDK" enum just to make those
points clear.

Then, we can *currently* make the "good providers" assumption,
but it could soon change since the plan was to also add algorithms
with known shortcomings.[1]

Gilles

[1] https://issues.apache.org/jira/browse/RNG-32

Alex

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

Reply via email to