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.

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.

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.

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

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

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.

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

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

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

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