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.
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
