Thread overview | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrew 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. |
June 11, 2012 Re: Mersenne Twister Seeding and UUIDs | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrew 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. |
June 11, 2012 Re: Mersenne Twister Seeding and UUIDs | ||||
---|---|---|---|---|
| ||||
Posted in reply to Johannes Pfau | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Joseph Rushton Wakeling | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Johannes Pfau | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jens Mueller | 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 |
Copyright © 1999-2021 by the D Language Foundation