You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Alex Herbert <al...@gmail.com> on 2019/04/10 12:46:37 UTC
[rng] nextInt(int) and nextLong(long) can be improved
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:
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.
Alex
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [rng] nextInt(int) and nextLong(long) can be improved
Posted by Gilles Sadowski <gi...@gmail.com>.
Le mer. 10 avr. 2019 à 18:26, Alex Herbert <al...@gmail.com> a écrit :
>
>
> On 10/04/2019 15:59, Gilles Sadowski wrote:
> > Hello.
> >
> > Le mer. 10 avr. 2019 à 15:22, Alex Herbert <al...@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-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [rng] nextInt(int) and nextLong(long) can be improved
Posted by Alex Herbert <al...@gmail.com>.
On 10/04/2019 15:59, Gilles Sadowski wrote:
> Hello.
>
> Le mer. 10 avr. 2019 à 15:22, Alex Herbert <al...@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-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [rng] nextInt(int) and nextLong(long) can be improved
Posted by Gilles Sadowski <gi...@gmail.com>.
Hello.
Le mer. 10 avr. 2019 à 15:22, Alex Herbert <al...@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-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [rng] nextInt(int) and nextLong(long) can be improved
Posted by Alex Herbert <al...@gmail.com>.
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 of
bits the change to use the lower order bits should be reasonable.
Alex
>
>
>
>
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org