[Math] New base class for all RNGs

classic Classic list List threaded Threaded
20 messages Options
Reply | Threaded
Open this post in threaded view
|

[Math] New base class for all RNGs

Gilles Sadowski
Hi.

There are currently two RNG hierarchies: "AbstractRandomGenerator" and
"BitsStreamGenerator". They both implement the "RandomGenerator"
interface.

In both classes, the "nextBytes(byte[])" method generates 4 bytes at a
time.
Thus, functionally the code is the same, even though one calls
"nextInt" and
the other "next(32)" (which is what its "nextInt()" also calls).

I propose that a new base class implements "nextBytes" (and perhaps
other
methods that can be coded in a generic way):
   https://issues.apache.org/jira/browse/MATH-1307

Are there objections?

Regards,
Gilles


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] New base class for all RNGs

Luc Maisonobe-2
Le 26/12/2015 18:52, Gilles a écrit :

> Hi.
>
> There are currently two RNG hierarchies: "AbstractRandomGenerator" and
> "BitsStreamGenerator". They both implement the "RandomGenerator" interface.
>
> In both classes, the "nextBytes(byte[])" method generates 4 bytes at a
> time.
> Thus, functionally the code is the same, even though one calls "nextInt"
> and
> the other "next(32)" (which is what its "nextInt()" also calls).
>
> I propose that a new base class implements "nextBytes" (and perhaps other
> methods that can be coded in a generic way):
>   https://issues.apache.org/jira/browse/MATH-1307
>
> Are there objections?

Go for it.

Luc

>
> Regards,
> Gilles
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] New base class for all RNGs

Phil Steitz
In reply to this post by Gilles Sadowski
On 12/26/15 10:52 AM, Gilles wrote:

> Hi.
>
> There are currently two RNG hierarchies: "AbstractRandomGenerator"
> and
> "BitsStreamGenerator". They both implement the "RandomGenerator"
> interface.
>
> In both classes, the "nextBytes(byte[])" method generates 4 bytes
> at a time.
> Thus, functionally the code is the same, even though one calls
> "nextInt" and
> the other "next(32)" (which is what its "nextInt()" also calls).
>
> I propose that a new base class implements "nextBytes" (and
> perhaps other
> methods that can be coded in a generic way):
>   https://issues.apache.org/jira/browse/MATH-1307
>
> Are there objections?

+1

Phil

>
> Regards,
> Gilles
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] New base class for all RNGs

Phil Steitz
In reply to this post by Gilles Sadowski
On 12/26/15 10:52 AM, Gilles wrote:

> Hi.
>
> There are currently two RNG hierarchies: "AbstractRandomGenerator"
> and
> "BitsStreamGenerator". They both implement the "RandomGenerator"
> interface.
>
> In both classes, the "nextBytes(byte[])" method generates 4 bytes
> at a time.
> Thus, functionally the code is the same, even though one calls
> "nextInt" and
> the other "next(32)" (which is what its "nextInt()" also calls).
>
> I propose that a new base class implements "nextBytes" (and
> perhaps other
> methods that can be coded in a generic way):
>   https://issues.apache.org/jira/browse/MATH-1307
>
> Are there objections?

Hey sorry I did not think to raise this possibility before, but it
could be we are letting archeaology complicate design here.  In 4.0
we can clean up what I think may be an early mistake.  The reason
that we have two hierarchies here is that AbstractRandomGenerator
predates BitStreamGenerator.  The AbstractRandomGenerator somewhat
iconoclastically basis things on nextDouble() while
BitStreamGenerator uses the more standard int next(int bits).  Note
that we have *no* internal direct implementations of
AbstractRandomGenerator, while BitStreamGenerator has worked very
nicely as a root for good PRNGs.

Therefore, I think for V4 it might actually be best to just drop
AbstractRandomGenerator.  Sorry I did not think of this before
responding above.

Phil

>
> Regards,
> Gilles
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>



---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] New base class for all RNGs

Gilles Sadowski
On Sat, 26 Dec 2015 15:32:04 -0700, Phil Steitz wrote:

> On 12/26/15 10:52 AM, Gilles wrote:
>> Hi.
>>
>> There are currently two RNG hierarchies: "AbstractRandomGenerator"
>> and
>> "BitsStreamGenerator". They both implement the "RandomGenerator"
>> interface.
>>
>> In both classes, the "nextBytes(byte[])" method generates 4 bytes
>> at a time.
>> Thus, functionally the code is the same, even though one calls
>> "nextInt" and
>> the other "next(32)" (which is what its "nextInt()" also calls).
>>
>> I propose that a new base class implements "nextBytes" (and
>> perhaps other
>> methods that can be coded in a generic way):
>>   https://issues.apache.org/jira/browse/MATH-1307
>>
>> Are there objections?
>
> Hey sorry I did not think to raise this possibility before, but it
> could be we are letting archeaology complicate design here.  In 4.0
> we can clean up what I think may be an early mistake.  The reason
> that we have two hierarchies here is that AbstractRandomGenerator
> predates BitStreamGenerator.  The AbstractRandomGenerator somewhat
> iconoclastically basis things on nextDouble() while
> BitStreamGenerator uses the more standard int next(int bits).  Note
> that we have *no* internal direct implementations of
> AbstractRandomGenerator, while BitStreamGenerator has worked very
> nicely as a root for good PRNGs.

Do you mean that "BitsStreamGenerator" can be the base class for
any RNG?

> Therefore, I think for V4 it might actually be best to just drop
> AbstractRandomGenerator.  Sorry I did not think of this before
> responding above.

Hmm.
Should I wait for confirmation before scratching it?

Then I have another question concerning "JDKRandomGenerator": it does
not fit in the hierarchy.

Gilles


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] New base class for all RNGs

Gilles Sadowski
In reply to this post by Phil Steitz
On Sat, 26 Dec 2015 15:32:04 -0700, Phil Steitz wrote:

> On 12/26/15 10:52 AM, Gilles wrote:
>> Hi.
>>
>> There are currently two RNG hierarchies: "AbstractRandomGenerator"
>> and
>> "BitsStreamGenerator". They both implement the "RandomGenerator"
>> interface.
>>
>> In both classes, the "nextBytes(byte[])" method generates 4 bytes
>> at a time.
>> Thus, functionally the code is the same, even though one calls
>> "nextInt" and
>> the other "next(32)" (which is what its "nextInt()" also calls).
>>
>> I propose that a new base class implements "nextBytes" (and
>> perhaps other
>> methods that can be coded in a generic way):
>>   https://issues.apache.org/jira/browse/MATH-1307
>>
>> Are there objections?
>
> Hey sorry I did not think to raise this possibility before, but it
> could be we are letting archeaology complicate design here.  In 4.0
> we can clean up what I think may be an early mistake.  The reason
> that we have two hierarchies here is that AbstractRandomGenerator
> predates BitStreamGenerator.  The AbstractRandomGenerator somewhat
> iconoclastically basis things on nextDouble() while
> BitStreamGenerator uses the more standard int next(int bits).  Note
> that we have *no* internal direct implementations of
> AbstractRandomGenerator, while BitStreamGenerator has worked very
> nicely as a root for good PRNGs.

Something implicit in "BitStreamGenerator": the maximum number of
bits is 32 (cf. return type of "next(int)" and the ubiquitous use
of hard-coded "32".

What about the possibility of using a "long" as a building block
for another family of RNG?

Gilles

>
> Therefore, I think for V4 it might actually be best to just drop
> AbstractRandomGenerator.  Sorry I did not think of this before
> responding above.
>
> Phil


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] New base class for all RNGs

Phil Steitz
In reply to this post by Gilles Sadowski


> On Dec 26, 2015, at 4:07 PM, Gilles <[hidden email]> wrote:
>
>> On Sat, 26 Dec 2015 15:32:04 -0700, Phil Steitz wrote:
>>> On 12/26/15 10:52 AM, Gilles wrote:
>>> Hi.
>>>
>>> There are currently two RNG hierarchies: "AbstractRandomGenerator"
>>> and
>>> "BitsStreamGenerator". They both implement the "RandomGenerator"
>>> interface.
>>>
>>> In both classes, the "nextBytes(byte[])" method generates 4 bytes
>>> at a time.
>>> Thus, functionally the code is the same, even though one calls
>>> "nextInt" and
>>> the other "next(32)" (which is what its "nextInt()" also calls).
>>>
>>> I propose that a new base class implements "nextBytes" (and
>>> perhaps other
>>> methods that can be coded in a generic way):
>>>  https://issues.apache.org/jira/browse/MATH-1307
>>>
>>> Are there objections?
>>
>> Hey sorry I did not think to raise this possibility before, but it
>> could be we are letting archeaology complicate design here.  In 4.0
>> we can clean up what I think may be an early mistake.  The reason
>> that we have two hierarchies here is that AbstractRandomGenerator
>> predates BitStreamGenerator.  The AbstractRandomGenerator somewhat
>> iconoclastically basis things on nextDouble() while
>> BitStreamGenerator uses the more standard int next(int bits).  Note
>> that we have *no* internal direct implementations of
>> AbstractRandomGenerator, while BitStreamGenerator has worked very
>> nicely as a root for good PRNGs.
>
> Do you mean that "BitsStreamGenerator" can be the base class for
> any RNG?

Yes

>
>> Therefore, I think for V4 it might actually be best to just drop
>> AbstractRandomGenerator.  Sorry I did not think of this before
>> responding above.
>
> Hmm.
> Should I wait for confirmation before scratching it?
>
> Then I have another question concerning "JDKRandomGenerator": it does
> not fit in the hierarchy.
>
> Gilles
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[Math] "BitsStreamGenerator" as base class for all RNGs (Was: New base class for all RNGs)

Gilles Sadowski
In reply to this post by Gilles Sadowski
Hi.

>> [...]
>> BitStreamGenerator uses the more standard int next(int bits).  Note
>> that we have *no* internal direct implementations of
>> AbstractRandomGenerator, while BitStreamGenerator has worked very
>> nicely as a root for good PRNGs.
>
> Something implicit in "BitStreamGenerator": the maximum number of
> bits is 32 (cf. return type of "next(int)" and the ubiquitous use
> of hard-coded "32".
>
> What about the possibility of using a "long" as a building block
> for another family of RNG?
>
> Gilles
>
>>
>> Therefore, I think for V4 it might actually be best to just drop
>> AbstractRandomGenerator.  Sorry I did not think of this before
>> responding above.
>>
>> Phil

(1)
Do all RNG that are going to ever be implemented in CM based on a
"int next(int)" method?

If not, then we can have a problem as soon as there is another
way to provide the random bits.

(2)
Assuming that we only need
   int next(int bits)

I notice that the source of random bits does indeed creates an "int",
say "x", and then truncates it before returning:

   protected int next(int bits) {
     // Build "x"...
     return x >>> 32 - bits;
   }

So, I believe that the actual basis for generating randomness should be
a "public abstract int nextInt()" method to be overridden by concrete
RNG producers (as "next(int)" currently is):

   @Override
   public int nextInt() {
     // Build "x"...
     return x;
   }

and the truncation should be performed inside the respective methods
that
currently call "next(int)". [Which are all in "BitsStreamGenerator".]
For example: replace the current

   public float nextFloat() {
     return next(23) * 0x1.0p-23f;
   }

by

   public float nextFloat() {
     return (nextInt() >>> 9) * 0x1.0p-23f;
   }

And, as a bonus, this will avoid the unnecessary
   x >>> (32 - 32)
operation currently performed when calling "next(32)".

OK?

If so, I propose to still create a new "BaseRandomGenerator" class that
will
be different from "BitsStreamGenerator" because of the above changes.

This class should be backported to MATH_3_X so that we can deprecate
"BitsStreamGenerator" in 3.6.



Gilles


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] "BitsStreamGenerator" as base class for all RNGs (Was: New base class for all RNGs)

Gilles Sadowski
On Sun, 27 Dec 2015 12:48:08 +0100, Gilles wrote:

> Hi.
>
>>> [...]
>>> BitStreamGenerator uses the more standard int next(int bits).  Note
>>> that we have *no* internal direct implementations of
>>> AbstractRandomGenerator, while BitStreamGenerator has worked very
>>> nicely as a root for good PRNGs.
>>
>> Something implicit in "BitStreamGenerator": the maximum number of
>> bits is 32 (cf. return type of "next(int)" and the ubiquitous use
>> of hard-coded "32".
>>
>> What about the possibility of using a "long" as a building block
>> for another family of RNG?
>>
>> Gilles
>>
>>>
>>> Therefore, I think for V4 it might actually be best to just drop
>>> AbstractRandomGenerator.  Sorry I did not think of this before
>>> responding above.
>>>
>>> Phil
>
> (1)
> Do all RNG that are going to ever be implemented in CM based on a
> "int next(int)" method?
>
> If not, then we can have a problem as soon as there is another
> way to provide the random bits.
>
> (2)
> Assuming that we only need
>   int next(int bits)
>
> I notice that the source of random bits does indeed creates an "int",
> say "x", and then truncates it before returning:
>
>   protected int next(int bits) {
>     // Build "x"...
>     return x >>> 32 - bits;
>   }
>
> So, I believe that the actual basis for generating randomness should
> be
> a "public abstract int nextInt()" method to be overridden by concrete
> RNG producers (as "next(int)" currently is):
>
>   @Override
>   public int nextInt() {
>     // Build "x"...
>     return x;
>   }
>
> and the truncation should be performed inside the respective methods
> that
> currently call "next(int)". [Which are all in "BitsStreamGenerator".]
> For example: replace the current
>
>   public float nextFloat() {
>     return next(23) * 0x1.0p-23f;
>   }
>
> by
>
>   public float nextFloat() {
>     return (nextInt() >>> 9) * 0x1.0p-23f;
>   }
>
> And, as a bonus, this will avoid the unnecessary
>   x >>> (32 - 32)
> operation currently performed when calling "next(32)".
>
> OK?
>
> If so, I propose to still create a new "BaseRandomGenerator" class
> that will
> be different from "BitsStreamGenerator" because of the above changes.
>
> This class should be backported to MATH_3_X so that we can deprecate
> "BitsStreamGenerator" in 3.6.
>

In addition to points (1) and (2) above, we should discuss the
following one.

(3)
Deprecate the "setSeed" methods (and also remove them from the
"RandomGenerator" interface).
The rationale is that they typically provide information for a
constructor;
they invalidate the previous state of the instance and imply the same
computation as is performed at construction.
[The only task not repeated by "setSeed" is the array(s) allocation.]

I thus propose that we use the fluent API, as we agreed to do in
general,
for the RNGs too. [I.e. a method "withSeed" will create a new
instance.]

This will also solve the potential security problem of having public
methods
called from the constructor.

Any objection?

Gilles


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] New base class for all RNGs

Phil Steitz
In reply to this post by Gilles Sadowski
On 12/26/15 4:52 PM, Gilles wrote:

> On Sat, 26 Dec 2015 15:32:04 -0700, Phil Steitz wrote:
>> On 12/26/15 10:52 AM, Gilles wrote:
>>> Hi.
>>>
>>> There are currently two RNG hierarchies: "AbstractRandomGenerator"
>>> and
>>> "BitsStreamGenerator". They both implement the "RandomGenerator"
>>> interface.
>>>
>>> In both classes, the "nextBytes(byte[])" method generates 4 bytes
>>> at a time.
>>> Thus, functionally the code is the same, even though one calls
>>> "nextInt" and
>>> the other "next(32)" (which is what its "nextInt()" also calls).
>>>
>>> I propose that a new base class implements "nextBytes" (and
>>> perhaps other
>>> methods that can be coded in a generic way):
>>>   https://issues.apache.org/jira/browse/MATH-1307
>>>
>>> Are there objections?
>>
>> Hey sorry I did not think to raise this possibility before, but it
>> could be we are letting archeaology complicate design here.  In 4.0
>> we can clean up what I think may be an early mistake.  The reason
>> that we have two hierarchies here is that AbstractRandomGenerator
>> predates BitStreamGenerator.  The AbstractRandomGenerator somewhat
>> iconoclastically basis things on nextDouble() while
>> BitStreamGenerator uses the more standard int next(int bits).  Note
>> that we have *no* internal direct implementations of
>> AbstractRandomGenerator, while BitStreamGenerator has worked very
>> nicely as a root for good PRNGs.
>
> Something implicit in "BitStreamGenerator": the maximum number of
> bits is 32 (cf. return type of "next(int)" and the ubiquitous use
> of hard-coded "32".
>
> What about the possibility of using a "long" as a building block
> for another family of RNG?

Why?  We don't have contributions of other RNGs implemented using
64-bit blocks of data.  In theory, I guess you could do that, but I
don't know of any and all the ones we have use 32-bit words.  

Phil

>
> Gilles
>
>>
>> Therefore, I think for V4 it might actually be best to just drop
>> AbstractRandomGenerator.  Sorry I did not think of this before
>> responding above.
>>
>> Phil
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>



---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] New base class for all RNGs

Phil Steitz
In reply to this post by Gilles Sadowski
On 12/26/15 4:07 PM, Gilles wrote:

> On Sat, 26 Dec 2015 15:32:04 -0700, Phil Steitz wrote:
>> On 12/26/15 10:52 AM, Gilles wrote:
>>> Hi.
>>>
>>> There are currently two RNG hierarchies: "AbstractRandomGenerator"
>>> and
>>> "BitsStreamGenerator". They both implement the "RandomGenerator"
>>> interface.
>>>
>>> In both classes, the "nextBytes(byte[])" method generates 4 bytes
>>> at a time.
>>> Thus, functionally the code is the same, even though one calls
>>> "nextInt" and
>>> the other "next(32)" (which is what its "nextInt()" also calls).
>>>
>>> I propose that a new base class implements "nextBytes" (and
>>> perhaps other
>>> methods that can be coded in a generic way):
>>>   https://issues.apache.org/jira/browse/MATH-1307
>>>
>>> Are there objections?
>>
>> Hey sorry I did not think to raise this possibility before, but it
>> could be we are letting archeaology complicate design here.  In 4.0
>> we can clean up what I think may be an early mistake.  The reason
>> that we have two hierarchies here is that AbstractRandomGenerator
>> predates BitStreamGenerator.  The AbstractRandomGenerator somewhat
>> iconoclastically basis things on nextDouble() while
>> BitStreamGenerator uses the more standard int next(int bits).  Note
>> that we have *no* internal direct implementations of
>> AbstractRandomGenerator, while BitStreamGenerator has worked very
>> nicely as a root for good PRNGs.
>
> Do you mean that "BitsStreamGenerator" can be the base class for
> any RNG?
>
>> Therefore, I think for V4 it might actually be best to just drop
>> AbstractRandomGenerator.  Sorry I did not think of this before
>> responding above.
>
> Hmm.
> Should I wait for confirmation before scratching it?
>
> Then I have another question concerning "JDKRandomGenerator": it does
> not fit in the hierarchy.

Right.  I don't personally think it *has* to fit in the hierarchy.
It exists only so that people can easily plug in the JDK-supplied
PRNG where [math] code expects a RandomGenerator.

Phil
>
> Gilles
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>



---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] "BitsStreamGenerator" as base class for all RNGs (Was: New base class for all RNGs)

Phil Steitz
In reply to this post by Gilles Sadowski
On 12/27/15 6:51 AM, Gilles wrote:

> On Sun, 27 Dec 2015 12:48:08 +0100, Gilles wrote:
>> Hi.
>>
>>>> [...]
>>>> BitStreamGenerator uses the more standard int next(int bits).
>>>> Note
>>>> that we have *no* internal direct implementations of
>>>> AbstractRandomGenerator, while BitStreamGenerator has worked very
>>>> nicely as a root for good PRNGs.
>>>
>>> Something implicit in "BitStreamGenerator": the maximum number of
>>> bits is 32 (cf. return type of "next(int)" and the ubiquitous use
>>> of hard-coded "32".
>>>
>>> What about the possibility of using a "long" as a building block
>>> for another family of RNG?
>>>
>>> Gilles
>>>
>>>>
>>>> Therefore, I think for V4 it might actually be best to just drop
>>>> AbstractRandomGenerator.  Sorry I did not think of this before
>>>> responding above.
>>>>
>>>> Phil
>>
>> (1)
>> Do all RNG that are going to ever be implemented in CM based on a
>> "int next(int)" method?
>>
>> If not, then we can have a problem as soon as there is another
>> way to provide the random bits.
>>
>> (2)
>> Assuming that we only need
>>   int next(int bits)
>>
>> I notice that the source of random bits does indeed creates an
>> "int",
>> say "x", and then truncates it before returning:
>>
>>   protected int next(int bits) {
>>     // Build "x"...
>>     return x >>> 32 - bits;
>>   }
>>
>> So, I believe that the actual basis for generating randomness
>> should be
>> a "public abstract int nextInt()" method to be overridden by
>> concrete
>> RNG producers (as "next(int)" currently is):
>>
>>   @Override
>>   public int nextInt() {
>>     // Build "x"...
>>     return x;
>>   }
>>
>> and the truncation should be performed inside the respective
>> methods that
>> currently call "next(int)". [Which are all in
>> "BitsStreamGenerator".]
>> For example: replace the current
>>
>>   public float nextFloat() {
>>     return next(23) * 0x1.0p-23f;
>>   }
>>
>> by
>>
>>   public float nextFloat() {
>>     return (nextInt() >>> 9) * 0x1.0p-23f;
>>   }
>>
>> And, as a bonus, this will avoid the unnecessary
>>   x >>> (32 - 32)
>> operation currently performed when calling "next(32)".
>>
>> OK?
>>
>> If so, I propose to still create a new "BaseRandomGenerator"
>> class that will
>> be different from "BitsStreamGenerator" because of the above
>> changes.
>>
>> This class should be backported to MATH_3_X so that we can deprecate
>> "BitsStreamGenerator" in 3.6.
>>
>
> In addition to points (1) and (2) above, we should discuss the
> following one.
>
> (3)
> Deprecate the "setSeed" methods (and also remove them from the
> "RandomGenerator" interface).

-1

The RandomGenerator interface is extracted from Random. As such, it
provides a simple way to plug in a [math]-supplied PRNG where Random
is used in code.  Dropping this method will force a lot of needless
refactoring.  The setSeed method exists as a convenience for users.
As one of those users, I don't want to see it go away.

Phil

> The rationale is that they typically provide information for a
> constructor;
> they invalidate the previous state of the instance and imply the same
> computation as is performed at construction.
> [The only task not repeated by "setSeed" is the array(s) allocation.]
>
> I thus propose that we use the fluent API, as we agreed to do in
> general,
> for the RNGs too. [I.e. a method "withSeed" will create a new
> instance.]
>
> This will also solve the potential security problem of having
> public methods
> called from the constructor.
>
> Any objection?
>
> Gilles
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] "BitsStreamGenerator" as base class for all RNGs

Gilles Sadowski
On Sun, 27 Dec 2015 11:15:42 -0700, Phil Steitz wrote:

> On 12/27/15 6:51 AM, Gilles wrote:
>> On Sun, 27 Dec 2015 12:48:08 +0100, Gilles wrote:
>>> Hi.
>>>
>>>>> [...]
>>>>> BitStreamGenerator uses the more standard int next(int bits).
>>>>> Note
>>>>> that we have *no* internal direct implementations of
>>>>> AbstractRandomGenerator, while BitStreamGenerator has worked very
>>>>> nicely as a root for good PRNGs.
>>>>
>>>> Something implicit in "BitStreamGenerator": the maximum number of
>>>> bits is 32 (cf. return type of "next(int)" and the ubiquitous use
>>>> of hard-coded "32".
>>>>
>>>> What about the possibility of using a "long" as a building block
>>>> for another family of RNG?
>>>>
>>>> Gilles
>>>>
>>>>>
>>>>> Therefore, I think for V4 it might actually be best to just drop
>>>>> AbstractRandomGenerator.  Sorry I did not think of this before
>>>>> responding above.
>>>>>
>>>>> Phil
>>>
>>> (1)
>>> Do all RNG that are going to ever be implemented in CM based on a
>>> "int next(int)" method?
>>>
>>> If not, then we can have a problem as soon as there is another
>>> way to provide the random bits.
>>>
>>> (2)
>>> Assuming that we only need
>>>   int next(int bits)
>>>
>>> I notice that the source of random bits does indeed creates an
>>> "int",
>>> say "x", and then truncates it before returning:
>>>
>>>   protected int next(int bits) {
>>>     // Build "x"...
>>>     return x >>> 32 - bits;
>>>   }
>>>
>>> So, I believe that the actual basis for generating randomness
>>> should be
>>> a "public abstract int nextInt()" method to be overridden by
>>> concrete
>>> RNG producers (as "next(int)" currently is):
>>>
>>>   @Override
>>>   public int nextInt() {
>>>     // Build "x"...
>>>     return x;
>>>   }
>>>
>>> and the truncation should be performed inside the respective
>>> methods that
>>> currently call "next(int)". [Which are all in
>>> "BitsStreamGenerator".]
>>> For example: replace the current
>>>
>>>   public float nextFloat() {
>>>     return next(23) * 0x1.0p-23f;
>>>   }
>>>
>>> by
>>>
>>>   public float nextFloat() {
>>>     return (nextInt() >>> 9) * 0x1.0p-23f;
>>>   }
>>>
>>> And, as a bonus, this will avoid the unnecessary
>>>   x >>> (32 - 32)
>>> operation currently performed when calling "next(32)".
>>>
>>> OK?
>>>
>>> If so, I propose to still create a new "BaseRandomGenerator"
>>> class that will
>>> be different from "BitsStreamGenerator" because of the above
>>> changes.
>>>
>>> This class should be backported to MATH_3_X so that we can
>>> deprecate
>>> "BitsStreamGenerator" in 3.6.
>>>
>>
>> In addition to points (1) and (2) above, we should discuss the
>> following one.
>>
>> (3)
>> Deprecate the "setSeed" methods (and also remove them from the
>> "RandomGenerator" interface).
>
> -1
>
> The RandomGenerator interface is extracted from Random. As such, it
> provides a simple way to plug in a [math]-supplied PRNG where Random
> is used in code.  Dropping this method will force a lot of needless
> refactoring.  The setSeed method exists as a convenience for users.
> As one of those users, I don't want to see it go away.

Never mind; I can fix the constructor safety problem with new
   private void setSeedInternal(/* ... */)
methods that will be called by their public counterparts.

Do we attempt to make the RNGs thread-safe?
It would mean that the "setSeed" methods must be made "synchronized".

More importantly, I'd like opinions on points (1) and (2) above...

In fact, you gave a partial answer to (1) in the other post, indicating
that CM does not have implementations other than the one producing an
"int", which I knew: The purpose of asking was whether we should be
expecting some change (like OS that went from 32 bits to 64 bits...).

If we care only for the present, then proposal (2) is OK I think.
Please confirm.


Gilles

> Phil
>> The rationale is that they typically provide information for a
>> constructor;
>> they invalidate the previous state of the instance and imply the
>> same
>> computation as is performed at construction.
>> [The only task not repeated by "setSeed" is the array(s)
>> allocation.]
>>
>> I thus propose that we use the fluent API, as we agreed to do in
>> general,
>> for the RNGs too. [I.e. a method "withSeed" will create a new
>> instance.]
>>
>> This will also solve the potential security problem of having
>> public methods
>> called from the constructor.
>>
>> Any objection?
>>
>> Gilles


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] "BitsStreamGenerator" as base class for all RNGs

Gilles Sadowski
>
> Do we attempt to make the RNGs thread-safe?
> It would mean that the "setSeed" methods must be made "synchronized".

"Not a problem", there is a "SynchronizedRandomGenerator" wrapper.

Gilles


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[Math] Add 64-bits based RNG (Was: [Math] New base class for all RNGs)

Gilles Sadowski
In reply to this post by Phil Steitz
Hi.

Relevant excerpt of previous posts:

>> [...]
>>
>> Something implicit in "BitStreamGenerator": the maximum number of
>> bits is 32 (cf. return type of "next(int)" and the ubiquitous use
>> of hard-coded "32".
>>
>> What about the possibility of using a "long" as a building block
>> for another family of RNG?
>
> Why?  We don't have contributions of other RNGs implemented using
> 64-bit blocks of data.  In theory, I guess you could do that, but I
> don't know of any and all the ones we have use 32-bit words.
>
> Phil
>>
>> Gilles

(1)
CPUs and OS are nowadays commonly 64-bits based.
Thus one could legitimately wonder whether, on such systems, generating
   one "long" value
would not be faster than generating
   two "int" values,
especially when 64 bits are necessary in order to produce the next
random
"long" or "double" value.

(2)
There indeed exist 64-bits implementations of RNGs:
   
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/mt19937-64.c
   http://burtleburtle.net/bob/rand/isaacafa.html


I thus propose to create a feature branch that will contain
* a new interface, for when "nextLong()" is the "random bits" producer
* the (adapted) "xorshift1024*" RNG implementation from
     http://xorshift.di.unimi.it/
* an "adapter" to the existing generic methods
* benchmarking code


Gilles


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] Add 64-bits based RNG (Was: [Math] New base class for all RNGs)

Phil Steitz
On Sat, Jan 9, 2016 at 9:09 PM, Gilles <[hidden email]> wrote:

> Hi.
>
> Relevant excerpt of previous posts:
>
> [...]
>>>
>>> Something implicit in "BitStreamGenerator": the maximum number of
>>> bits is 32 (cf. return type of "next(int)" and the ubiquitous use
>>> of hard-coded "32".
>>>
>>> What about the possibility of using a "long" as a building block
>>> for another family of RNG?
>>>
>>
>> Why?  We don't have contributions of other RNGs implemented using
>> 64-bit blocks of data.  In theory, I guess you could do that, but I
>> don't know of any and all the ones we have use 32-bit words.
>>
>> Phil
>>
>>>
>>> Gilles
>>>
>>
> (1)
> CPUs and OS are nowadays commonly 64-bits based.
> Thus one could legitimately wonder whether, on such systems, generating
>   one "long" value
> would not be faster than generating
>   two "int" values,
> especially when 64 bits are necessary in order to produce the next random
> "long" or "double" value.
>
(2)
> There indeed exist 64-bits implementations of RNGs:
>
> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/mt19937-64.c
>   http://burtleburtle.net/bob/rand/isaacafa.html
>
>
> I thus propose to create a feature branch that will contain
> * a new interface, for when "nextLong()" is the "random bits" producer
>

You mean another abstract base class.  Fine by me.


> * the (adapted) "xorshift1024*" RNG implementation from
>     http://xorshift.di.unimi.it/


+1 to add a new one, assuming someone is willing to do the research and get
a clean impl.  Looks like the above is GPL, so we have to be careful will
adapting code.  The benchmarks and discussion there look promising, though.


>
> * an "adapter" to the existing generic methods
>

What do you mean by this?

* benchmarking code
>

+1

Phil

>
>
> Gilles
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>
Reply | Threaded
Open this post in threaded view
|

Re: [Math] Add 64-bits based RNG (Was: [Math] New base class for all RNGs)

Thomas Neidhart
In reply to this post by Gilles Sadowski
On 01/10/2016 05:09 AM, Gilles wrote:

> Hi.
>
> Relevant excerpt of previous posts:
>
>>> [...]
>>>
>>> Something implicit in "BitStreamGenerator": the maximum number of
>>> bits is 32 (cf. return type of "next(int)" and the ubiquitous use
>>> of hard-coded "32".
>>>
>>> What about the possibility of using a "long" as a building block
>>> for another family of RNG?
>>
>> Why?  We don't have contributions of other RNGs implemented using
>> 64-bit blocks of data.  In theory, I guess you could do that, but I
>> don't know of any and all the ones we have use 32-bit words.
>>
>> Phil
>>>
>>> Gilles
>
> (1)
> CPUs and OS are nowadays commonly 64-bits based.
> Thus one could legitimately wonder whether, on such systems, generating
>   one "long" value
> would not be faster than generating
>   two "int" values,
> especially when 64 bits are necessary in order to produce the next random
> "long" or "double" value.
>
> (2)
> There indeed exist 64-bits implementations of RNGs:
>  
> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/mt19937-64.c
>
>   http://burtleburtle.net/bob/rand/isaacafa.html
>
>
> I thus propose to create a feature branch that will contain
> * a new interface, for when "nextLong()" is the "random bits" producer

be aware that (at least some of) the 64-bit variants rely on unsigned
long arithmetic operations which can't be done in java without losing a
*lot* performance.

Thomas

> * the (adapted) "xorshift1024*" RNG implementation from
>     http://xorshift.di.unimi.it/
> * an "adapter" to the existing generic methods
> * benchmarking code
>
>
> Gilles
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] Add 64-bits based RNG (Was: [Math] New base class for all RNGs)

Gilles Sadowski
On Mon, 11 Jan 2016 07:47:40 +0100, Thomas Neidhart wrote:

> On 01/10/2016 05:09 AM, Gilles wrote:
>> Hi.
>>
>> Relevant excerpt of previous posts:
>>
>>>> [...]
>>>>
>>>> Something implicit in "BitStreamGenerator": the maximum number of
>>>> bits is 32 (cf. return type of "next(int)" and the ubiquitous use
>>>> of hard-coded "32".
>>>>
>>>> What about the possibility of using a "long" as a building block
>>>> for another family of RNG?
>>>
>>> Why?  We don't have contributions of other RNGs implemented using
>>> 64-bit blocks of data.  In theory, I guess you could do that, but I
>>> don't know of any and all the ones we have use 32-bit words.
>>>
>>> Phil
>>>>
>>>> Gilles
>>
>> (1)
>> CPUs and OS are nowadays commonly 64-bits based.
>> Thus one could legitimately wonder whether, on such systems,
>> generating
>>   one "long" value
>> would not be faster than generating
>>   two "int" values,
>> especially when 64 bits are necessary in order to produce the next
>> random
>> "long" or "double" value.
>>
>> (2)
>> There indeed exist 64-bits implementations of RNGs:
>>
>>
>> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/mt19937-64.c
>>
>>   http://burtleburtle.net/bob/rand/isaacafa.html
>>
>>
>> I thus propose to create a feature branch that will contain
>> * a new interface, for when "nextLong()" is the "random bits"
>> producer
>
> be aware that (at least some of) the 64-bit variants rely on unsigned
> long arithmetic operations which can't be done in java without losing
> a
> *lot* performance.

What do you mean?

Wasn't there the same problem when implementing RNGs that rely on
unsigned int arithmetic, with Java's signed int?

But IIUC, the RNG codes generally rely on bit operations (and bit
operations disguised as arithmetic).[1]
Fortunately, the representation is the same in C and Java, which
allows us to mostly copy source code.
There *are* caveats, though:
   * ">>" in C code must (in general) be replaced with ">>>"
   * Some constants (that exceed MAX_VALUE) cannot be written using
     their decimal representation (hexadecimal must be used instead).

Gilles

[1] This is related to the "next(int bits)" debate: Ideally, an
     RNG indeed provides a "bit stream" but, as we are now all
     hopefully convinced, those that concern us in CM actually
     manipulate "int" (or "long") values, not "boolean" sequences.

> Thomas
>
>> * the (adapted) "xorshift1024*" RNG implementation from
>>     http://xorshift.di.unimi.it/
>> * an "adapter" to the existing generic methods
>> * benchmarking code
>>
>>
>> Gilles
>>


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] Add 64-bits based RNG (Was: [Math] New base class for all RNGs)

Thomas Neidhart
On Mon, Jan 11, 2016 at 1:10 PM, Gilles <[hidden email]>
wrote:

> On Mon, 11 Jan 2016 07:47:40 +0100, Thomas Neidhart wrote:
>
>> On 01/10/2016 05:09 AM, Gilles wrote:
>>
>>> Hi.
>>>
>>> Relevant excerpt of previous posts:
>>>
>>> [...]
>>>>>
>>>>> Something implicit in "BitStreamGenerator": the maximum number of
>>>>> bits is 32 (cf. return type of "next(int)" and the ubiquitous use
>>>>> of hard-coded "32".
>>>>>
>>>>> What about the possibility of using a "long" as a building block
>>>>> for another family of RNG?
>>>>>
>>>>
>>>> Why?  We don't have contributions of other RNGs implemented using
>>>> 64-bit blocks of data.  In theory, I guess you could do that, but I
>>>> don't know of any and all the ones we have use 32-bit words.
>>>>
>>>> Phil
>>>>
>>>>>
>>>>> Gilles
>>>>>
>>>>
>>> (1)
>>> CPUs and OS are nowadays commonly 64-bits based.
>>> Thus one could legitimately wonder whether, on such systems, generating
>>>   one "long" value
>>> would not be faster than generating
>>>   two "int" values,
>>> especially when 64 bits are necessary in order to produce the next random
>>> "long" or "double" value.
>>>
>>> (2)
>>> There indeed exist 64-bits implementations of RNGs:
>>>
>>>
>>>
>>> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/mt19937-64.c
>>>
>>>   http://burtleburtle.net/bob/rand/isaacafa.html
>>>
>>>
>>> I thus propose to create a feature branch that will contain
>>> * a new interface, for when "nextLong()" is the "random bits" producer
>>>
>>
>> be aware that (at least some of) the 64-bit variants rely on unsigned
>> long arithmetic operations which can't be done in java without losing a
>> *lot* performance.
>>
>
> What do you mean?
>
> Wasn't there the same problem when implementing RNGs that rely on
> unsigned int arithmetic, with Java's signed int?
>

in which case you can perform the operation in longs and convert back to
ints.
This is actually done for some of the RNG implementations in CM.

Normally, the addition, subtraction and multiplication should be
unaffected. Problematic are division (modulo) and comparison,
which need to be treated specially. At least the Well type rngs do modulo
operations, but I did not look into detail if this would create problems.

I just wanted to raise this issue before any decision is being made.


>
> But IIUC, the RNG codes generally rely on bit operations (and bit
> operations disguised as arithmetic).[1]
> Fortunately, the representation is the same in C and Java, which
> allows us to mostly copy source code.
> There *are* caveats, though:
>   * ">>" in C code must (in general) be replaced with ">>>"
>   * Some constants (that exceed MAX_VALUE) cannot be written using
>     their decimal representation (hexadecimal must be used instead).
>

the ">>" operator in C is implementation specific for signed values (see
http://stackoverflow.com/questions/7622/shift-operator-in-c).
Replacing it blindly with ">>>" is not correct imho.

Thomas


> Gilles
>
> [1] This is related to the "next(int bits)" debate: Ideally, an
>     RNG indeed provides a "bit stream" but, as we are now all
>     hopefully convinced, those that concern us in CM actually
>     manipulate "int" (or "long") values, not "boolean" sequences.
>
>
> Thomas
>>
>> * the (adapted) "xorshift1024*" RNG implementation from
>>>     http://xorshift.di.unimi.it/
>>> * an "adapter" to the existing generic methods
>>> * benchmarking code
>>>
>>>
>>> Gilles
>>>
>>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>
Reply | Threaded
Open this post in threaded view
|

Re: [Math] Add 64-bits based RNG (Was: [Math] New base class for all RNGs)

Bernd Eckenfels
In reply to this post by Gilles Sadowski
BTW, there are some unsignedLong supporting methods in Java 8, I think some of them are even intrinsics, this includes unsigned parsing, printing, comparision and division/reminder. I think not yet a modular add.

https://docs.oracle.com/javase/8/docs/api/java/lang/Long.html#remainderUnsigned-long-long-

Gruss
Bernd
--
http://bernd.eckenfels.net

-----Original Message-----
From: Thomas Neidhart <[hidden email]>
To: Commons Developers List <[hidden email]>
Sent: Mo., 11 Jan. 2016 7:47
Subject: Re: [Math] Add 64-bits based RNG (Was: [Math] New base class for all RNGs)

On 01/10/2016 05:09 AM, Gilles wrote:

> Hi.
>
> Relevant excerpt of previous posts:
>
>>> [...]
>>>
>>> Something implicit in "BitStreamGenerator": the maximum number of
>>> bits is 32 (cf. return type of "next(int)" and the ubiquitous use
>>> of hard-coded "32".
>>>
>>> What about the possibility of using a "long" as a building block
>>> for another family of RNG?
>>
>> Why?  We don't have contributions of other RNGs implemented using
>> 64-bit blocks of data.  In theory, I guess you could do that, but I
>> don't know of any and all the ones we have use 32-bit words.
>>
>> Phil
>>>
>>> Gilles
>
> (1)
> CPUs and OS are nowadays commonly 64-bits based.
> Thus one could legitimately wonder whether, on such systems, generating
>   one "long" value
> would not be faster than generating
>   two "int" values,
> especially when 64 bits are necessary in order to produce the next random
> "long" or "double" value.
>
> (2)
> There indeed exist 64-bits implementations of RNGs:
>  
> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/mt19937-64.c
>
>   http://burtleburtle.net/bob/rand/isaacafa.html
>
>
> I thus propose to create a feature branch that will contain
> * a new interface, for when "nextLong()" is the "random bits" producer

be aware that (at least some of) the 64-bit variants rely on unsigned
long arithmetic operations which can't be done in java without losing a
*lot* performance.

Thomas

> * the (adapted) "xorshift1024*" RNG implementation from
>     http://xorshift.di.unimi.it/
> * an "adapter" to the existing generic methods
> * benchmarking code
>
>
> Gilles
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]