View mode: basic / threaded / horizontal-split · Log in · Help
June 09, 2012
Mersenne Twister Seeding and UUIDs
Forgive what may be the unintelligible ramblings of an ignorant hobbyist, 
but, if I am not mistaken, the Mersenne Twister implementation in std.random 
currently can be seeded only with a 32-bit unsigned integer, which I presume 
gives it 2^32 starting points, whereas I believe there should also be an 
alternative option to seed it with an array of up to 624 uintS, so that 
potentially it can be started in any one of its 19,937 internal states. I 
may be wrong, but I believe that to have instant access to enough of the 
"state space" to be able to generate a large number of unique random UUIDs 
this second seeding option may be necessary.

-- 
Andy Talbot.
June 10, 2012
Re: Mersenne Twister Seeding and UUIDs
Andrew Talbot wrote:

> which I presume gives it 2^32 starting points, whereas I believe there
> should also be an alternative option to seed it with an array of up to 624
> uintS, so that potentially it can be started in any one of its 19,937
> internal states.

Of course I meant "...in any one of its 2^19,937 internal states".

-- 
Andy Talbot.
June 11, 2012
Re: Mersenne Twister Seeding and UUIDs
Am Sun, 10 Jun 2012 00:24 +0100
schrieb Andrew Talbot <andrew.talbot@talbotville.com>:

> Forgive what may be the unintelligible ramblings of an ignorant
> hobbyist, but, if I am not mistaken, the Mersenne Twister
> implementation in std.random currently can be seeded only with a
> 32-bit unsigned integer, which I presume gives it 2^32 starting
> points, whereas I believe there should also be an alternative option
> to seed it with an array of up to 624 uintS, so that potentially it
> can be started in any one of its 19,937 internal states. I may be
> wrong, but I believe that to have instant access to enough of the
> "state space" to be able to generate a large number of unique random
> UUIDs this second seeding option may be necessary.
> 

Could someone who's familiar with RNGs answer this question? This seems
to be important for st.uuid, we should get this right.
June 11, 2012
Re: Mersenne Twister Seeding and UUIDs
On 11/06/12 18:15, Johannes Pfau wrote:
> Am Sun, 10 Jun 2012 00:24 +0100
> schrieb Andrew Talbot<andrew.talbot@talbotville.com>:
>
>> Forgive what may be the unintelligible ramblings of an ignorant
>> hobbyist, but, if I am not mistaken, the Mersenne Twister
>> implementation in std.random currently can be seeded only with a
>> 32-bit unsigned integer, which I presume gives it 2^32 starting
>> points, whereas I believe there should also be an alternative option
>> to seed it with an array of up to 624 uintS, so that potentially it
>> can be started in any one of its 19,937 internal states. I may be
>> wrong, but I believe that to have instant access to enough of the
>> "state space" to be able to generate a large number of unique random
>> UUIDs this second seeding option may be necessary.
>>
>
> Could someone who's familiar with RNGs answer this question? This seems
> to be important for st.uuid, we should get this right.

In the Boost C++ implementation it certainly accepts a range as input:

  template<class It>
  void seed(It& first, It last)
  {
    int j;
    for(j = 0; j < n && first != last; ++j, ++first)
      x[j] = *first;
    i = n;
    if(first == last && j < n)
      throw std::invalid_argument("mersenne_twister::seed");
  }

Some information on the seeding issue can be found here:
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html
June 11, 2012
Re: Mersenne Twister Seeding and UUIDs
On 6/11/12 12:32 PM, Joseph Rushton Wakeling wrote:
> On 11/06/12 18:15, Johannes Pfau wrote:
>> Could someone who's familiar with RNGs answer this question? This seems
>> to be important for st.uuid, we should get this right.
>
> In the Boost C++ implementation it certainly accepts a range as input:
>
> template<class It>
> void seed(It& first, It last)
> {
> int j;
> for(j = 0; j < n && first != last; ++j, ++first)
> x[j] = *first;
> i = n;
> if(first == last && j < n)
> throw std::invalid_argument("mersenne_twister::seed");
> }
>
> Some information on the seeding issue can be found here:
> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html

We should have the same in std.random. Could anyone please initiate a 
pull request?

Thanks,

Andrei
June 12, 2012
Re: Mersenne Twister Seeding and UUIDs
Am Mon, 11 Jun 2012 13:09:26 -0500
schrieb Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org>:

> On 6/11/12 12:32 PM, Joseph Rushton Wakeling wrote:
> > On 11/06/12 18:15, Johannes Pfau wrote:
> >> Could someone who's familiar with RNGs answer this question? This
> >> seems to be important for st.uuid, we should get this right.
> >
> > In the Boost C++ implementation it certainly accepts a range as
> > input:
> >
> > template<class It>
> > void seed(It& first, It last)
> > {
> > int j;
> > for(j = 0; j < n && first != last; ++j, ++first)
> > x[j] = *first;
> > i = n;
> > if(first == last && j < n)
> > throw std::invalid_argument("mersenne_twister::seed");
> > }
> >
> > Some information on the seeding issue can be found here:
> > http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html
> 
> We should have the same in std.random. Could anyone please initiate a 
> pull request?
> 
> Thanks,
> 
> Andrei

Here's a first try:
https://gist.github.com/2916360

Three questions:

* As seed is a normal function right now, I can't overload it with a
 template. Is it safe to make the original seed a template as well, so
 seedRange could be named seed, or would that break the API?

* How should the seed array/range be generated? By repeatedly calling
 unpredictableSeed?

* Is there a Range which repeatedly calls a function? Similar to
 repeat, but not repeating a value.
June 12, 2012
Re: Mersenne Twister Seeding and UUIDs
Johannes Pfau wrote:
> Am Mon, 11 Jun 2012 13:09:26 -0500
> schrieb Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org>:
> 
> > On 6/11/12 12:32 PM, Joseph Rushton Wakeling wrote:
> > > On 11/06/12 18:15, Johannes Pfau wrote:
> > >> Could someone who's familiar with RNGs answer this question? This
> > >> seems to be important for st.uuid, we should get this right.
> > >
> > > In the Boost C++ implementation it certainly accepts a range as
> > > input:
> > >
> > > template<class It>
> > > void seed(It& first, It last)
> > > {
> > > int j;
> > > for(j = 0; j < n && first != last; ++j, ++first)
> > > x[j] = *first;
> > > i = n;
> > > if(first == last && j < n)
> > > throw std::invalid_argument("mersenne_twister::seed");
> > > }
> > >
> > > Some information on the seeding issue can be found here:
> > > http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html
> > 
> > We should have the same in std.random. Could anyone please initiate a 
> > pull request?
> > 
> > Thanks,
> > 
> > Andrei
> 
> Here's a first try:
> https://gist.github.com/2916360
> 
> Three questions:
> 
> * As seed is a normal function right now, I can't overload it with a
>   template. Is it safe to make the original seed a template as well, so
>   seedRange could be named seed, or would that break the API?

What do you mean by you can't overload it? Does it not compile? I think
it should.

> * How should the seed array/range be generated? By repeatedly calling
>   unpredictableSeed?

No idea what is recommended from cryptographic point of view.

> * Is there a Range which repeatedly calls a function? Similar to
>   repeat, but not repeating a value.

Here is one way to do it.
seedRange(map!((a) => unpredictableSeed)(iota(0, 624)));
Probably, there is a more straightforward way.

I simplified your code a bit.

enum n = 624;
enforce(range.length >= n, "MersenneTwisterEngine.seedRange: Input range didn't provide enough"
                          " elements");
uint mt[];
mt.length = n;
copy(range, mt);

But I'm unsure whether it still does what you intended.

Jens
June 12, 2012
Re: Mersenne Twister Seeding and UUIDs
On Tuesday, June 12, 2012 11:48:11 Jens Mueller wrote:
> Johannes Pfau wrote:
> > * As seed is a normal function right now, I can't overload it with a
> > 
> >   template. Is it safe to make the original seed a template as well, so
> >   seedRange could be named seed, or would that break the API?
> 
> What do you mean by you can't overload it? Does it not compile? I think
> it should.

You can't currently overload templated functions with non-templated functions 
or vice versa:

http://d.puremagic.com/issues/show_bug.cgi?id=1528

The solution is to just give the non-templated functions an empty template 
parameter list. It shouldn't break any code. Worst case, you might have to add 
constraints to the fully templated version to make it so that it doesn't match 
any of the arguments that the formerly non-templated function accepts.

- Jonathan M Davis
June 12, 2012
Re: Mersenne Twister Seeding and UUIDs
Jonathan M Davis wrote:
> On Tuesday, June 12, 2012 11:48:11 Jens Mueller wrote:
> > Johannes Pfau wrote:
> > > * As seed is a normal function right now, I can't overload it with a
> > > 
> > >   template. Is it safe to make the original seed a template as well, so
> > >   seedRange could be named seed, or would that break the API?
> > 
> > What do you mean by you can't overload it? Does it not compile? I think
> > it should.
> 
> You can't currently overload templated functions with non-templated functions 
> or vice versa:
> 
> http://d.puremagic.com/issues/show_bug.cgi?id=1528
> 
> The solution is to just give the non-templated functions an empty template 
> parameter list. It shouldn't break any code. Worst case, you might have to add 
> constraints to the fully templated version to make it so that it doesn't match 
> any of the arguments that the formerly non-templated function accepts.

Thanks, I didn't know. Better said I forgot. Because I already voted on
this issue.

Jens
June 12, 2012
Re: Mersenne Twister Seeding and UUIDs
Am Tue, 12 Jun 2012 11:48:11 +0200
schrieb Jens Mueller <jens.k.mueller@gmx.de>:

> > * As seed is a normal function right now, I can't overload it with a
> >   template. Is it safe to make the original seed a template as
> > well, so seedRange could be named seed, or would that break the API?
> 
> What do you mean by you can't overload it? Does it not compile? I
> think it should.
> 
> > * How should the seed array/range be generated? By repeatedly
> > calling unpredictableSeed?
> 
> No idea what is recommended from cryptographic point of view.
> 
> > * Is there a Range which repeatedly calls a function? Similar to
> >   repeat, but not repeating a value.
> 
> Here is one way to do it.
> seedRange(map!((a) => unpredictableSeed)(iota(0, 624)));
> Probably, there is a more straightforward way.

Thanks, that's good enough. It would be even better if it was an
infinite range, though.

> I simplified your code a bit.
> 
> enum n = 624;
> enforce(range.length >= n, "MersenneTwisterEngine.seedRange: Input
> range didn't provide enough" " elements");

I can't really use .length, the code has to work with infinite ranges
as well.

> uint mt[];
> mt.length = n;
> copy(range, mt);
> 
> But I'm unsure whether it still does what you intended.

Well, the code was a simple 1:1 port of the boost function and as I'm
not familiar with RNGs I don't really want to change (and probably
break) it.

> 
> Jens
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home