Le mer. 10 avr. 2019 à 18:26, Alex Herbert <alex.d.herb...@gmail.com> a écrit :
>
>
> 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).
+1
> 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.
+1
> 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?
Fine.
Gilles
> > 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
