www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - dxorshift: random number generators from the extended Xorshift family

reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
http://code.dlang.org/packages/dxorshift
https://github.com/WebDrake/dxorshift

Following my earlier list posting 
<http://forum.dlang.org/post/kdobdorqztlsomweftmi forum.dlang.org>, I'm pleased
to announce an initial release of a dub package providing some of the RNGs from
the extended family of xorshift-inspired generators.  These should complement
the existing xorshift implementations already provided to Phobos' std.random by
Masahiro Nakagawa: they are fast, high-quality generators representing some of
the state of the art in pseudo-RNG design.

The generators implemented have been ported from public-domain 
reference implementations available here: 
http://xoroshiro.di.unimi.it/  Following the original authors' 
example, these D ports have also been dedicated to the public 
domain using the Creative Commons CC0 license.

At this stage, only a direct port has been provided, with no 
attempts at generics (e.g. on the unsigned integer type used, or 
the magic constants used in the RNG update methods).  The 
provided generators are:

   * SplitMix64: a fast generator with only 64 bits
     of state; this is probably inadequate for any
     serious statistical work, but is provided as a
     convenient means of generating seeds for other
     more heavy-duty algorithms

   * xoroshiro128+: a very fast and high quality
     generator with 128 bits of state; this ought
     to be a great generator for anyone not doing
     massively parallel simulations

   * xorshift1024*: a very fast and high quality
     generator with 1024 bits of state; this is
     slower than xoroshiro128+, but can be used
     with much larger-scale parallel simulations

The xoroshiro128+ and xorshift1024* generators come with `jump()` 
methods, the equivalent of 2 ^^ 64 and 2 ^^ 512 calls to 
`popFront()` respectively, which can be used to generate the 
starting points for (again respectively) 2 ^^ 64 or 2 ^^ 512 
independent sequences of variates.

The generators are all implemented as structs, but in order to 
prevent some known problems with unintended copy-by-value of 
RNGs, the postblit has been disabled.  For similar reasons, these 
generators are implemented as input ranges, not forward ranges, 
so that library functionality cannot copy generator state under 
the hood.

`dup` properties are however provided for all generators, to 
allow the programmer to deliberately copy RNG state.

Testing, feedback and general usage are all welcome.  I am 
planning on submitting these to Phobos (although sorting out the 
generic side of things might be a good idea first).
May 15 2016
parent reply Basile B. <b2.temp gmx.com> writes:
On Sunday, 15 May 2016 at 09:20:22 UTC, Joseph Rushton Wakeling 
wrote:
 http://code.dlang.org/packages/dxorshift
 https://github.com/WebDrake/dxorshift

 [...]

 The generators are all implemented as structs, but in order to 
 prevent some known problems with unintended copy-by-value of 
 RNGs, the postblit has been disabled.  For similar reasons, 
 these generators are implemented as input ranges, not forward 
 ranges, so that library functionality cannot copy generator 
 state under the hood.

 `dup` properties are however provided for all generators, to 
 allow the programmer to deliberately copy RNG state.

 Testing, feedback and general usage are all welcome.  I am 
 planning on submitting these to Phobos (although sorting out 
 the generic side of things might be a good idea first).
Nice, The " disable this" is really a concern, because pointers have to be used (for example if the seed comes from a program option and that the gen is a global var then global var must be a pointer to the stuff). I see that you are yourself affected by the issue because in the unittest you must take the gen address to use it in take . The main consequence is that they are unsable in safe code !
May 15 2016
parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On Sunday, 15 May 2016 at 10:35:11 UTC, Basile B. wrote:
 The " disable this" is really a concern, because pointers have 
 to be used (for example if the seed comes from a program option 
 and that the gen is a global var then global var must be a 
 pointer to the stuff).

 I see that you are yourself affected by the issue because in 
 the unittest you must take the gen address to use it in take   .

 The main consequence is that they are unsable in  safe code !
The safe side of things is obviously a concern, but having safe code is not very helpful if you don't also have _statistical_ safety. See what happens with phobos RNGs if you try, import std.stdio : writeln; import std.random : Random, unpredictableSeed import std.range : take; auto gen = Random(unpredictableSeed); gen.take(10).writeln; gen.take(10).writeln; ... ;-) Probably the best way to handle this is to handle the take-the-address side of things by a trusted wrapper that uses `return ref` to guarantee the pointer remains valid for the lifetime of the wrapper itself.
May 15 2016
parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On Sunday, 15 May 2016 at 10:43:55 UTC, Joseph Rushton Wakeling 
wrote:
 Probably the best way to handle this is to handle the 
 take-the-address side of things by a  trusted wrapper that uses 
 `return ref` to guarantee the pointer remains valid for the 
 lifetime of the wrapper itself.
Note, I've been mulling over this myself for a while, so I'll probably put something together in a future dxorshift release (and probably try to get it in Phobos ASAP, as it will be very helpful in avoiding the worst cases of the existing RNG functionality).
May 15 2016
next sibling parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On Sunday, 15 May 2016 at 11:15:38 UTC, Joseph Rushton Wakeling 
wrote:
 On Sunday, 15 May 2016 at 10:43:55 UTC, Joseph Rushton Wakeling 
 wrote:
 Probably the best way to handle this is to handle the 
 take-the-address side of things by a  trusted wrapper that 
 uses `return ref` to guarantee the pointer remains valid for 
 the lifetime of the wrapper itself.
Note, I've been mulling over this myself for a while, so I'll probably put something together in a future dxorshift release (and probably try to get it in Phobos ASAP, as it will be very helpful in avoiding the worst cases of the existing RNG functionality).
Sneak preview to try out, before I tidy this up for actual inclusion in the library (needs docs, etc): ///////////////////////////////////////////////////////////////////// module dxorshift.wrapper; import std.random : isUniformRNG; public struct SafeUniformRNG (BaseRNG) if (isUniformRNG!BaseRNG) { public: this (return ref BaseRNG generator) trusted { this.gen = &generator; } enum isUniformRandom = BaseRNG.isUniformRandom; bool empty() property { return this.gen.empty; } auto front() property { return this.gen.front; } auto popFront() { this.gen.popFront(); } auto seed(Seed...)(Seed s) { this.gen.seed(s); } private: BaseRNG* gen; invariant() { assert(this.gen !is null); } } public auto uniformRNG(BaseRNG)(return ref BaseRNG generator) { return SafeUniformRNG!BaseRNG(generator); } // test `uniformRNG`'s behavior with phobos RNGs safe unittest { import std.array : array; import std.random : isUniformRNG, isSeedable, PseudoRngTypes; import std.range.primitives : isInputRange, isForwardRange; import std.range : take; foreach (RNG; PseudoRngTypes) { alias SafeRNG = SafeUniformRNG!RNG; static assert(isUniformRNG!SafeRNG); static assert(isSeedable!SafeRNG == isSeedable!RNG); static assert(isInputRange!SafeRNG); static assert(!isForwardRange!SafeRNG); // assuming RNG is seedable, we validate // expected differences between phobos // RNGs' normal behaviour and how they // behave when wrapped by `uniformRNG` static if (isSeedable!RNG) { RNG gen; gen.seed(123456); // if we pass any normal phobos RNG // directly into a range chain, it // will (sadly) be copied by value auto take1 = gen.take(10).array; auto take2 = gen.take(10).array; assert(take1 == take2); gen.seed(123456); // if however we wrap it with `uniformRNG` // it will be passed by reference auto safeGen = uniformRNG(gen); auto take3 = safeGen.take(10).array; auto take4 = safeGen.take(10).array; assert(take3 == take1); // because we start from the same seed assert(take3 != take4); // validate we can however re-seed the // safely wrapped generator and get // the same results once again safeGen.seed(123456); auto take5 = safeGen.take(10).array; auto take6 = safeGen.take(10).array; assert(take5 == take3); assert(take6 == take4); } } } // validate it works with dxorshift RNGs // and allows them to work in safe code safe nothrow pure unittest { import std.array : array; import std.meta : AliasSeq; import std.random : isUniformRNG, isSeedable; import std.range.primitives : isInputRange, isForwardRange; import std.range : take; import dxorshift : SplitMix64, Xoroshiro128plus, Xorshift1024star; foreach (RNG; AliasSeq!(SplitMix64, Xoroshiro128plus, Xorshift1024star)) { alias SafeRNG = SafeUniformRNG!RNG; static assert(isUniformRNG!SafeRNG); static assert(isSeedable!SafeRNG); static assert(isInputRange!SafeRNG); static assert(!isForwardRange!SafeRNG); // dxorshift generators must be constructed // with a seed auto gen = RNG(123456); // we can't copy dxorshift RNGs by value, // and it's not safe to just take the // pointer address, so let's just jump // to wrapping them in `uniformRNG` auto safeGen = uniformRNG(gen); auto take1 = safeGen.take(10).array; auto take2 = safeGen.take(10).array; assert(take1 != take2); // re-seeding should give us the same // results once over gen.seed(123456); auto take3 = safeGen.take(10).array; auto take4 = safeGen.take(10).array; assert(take3 == take1); assert(take4 == take2); // re-seeding via the safe wrapper // should produce the same results safeGen.seed(123456); auto take5 = safeGen.take(10).array; auto take6 = safeGen.take(10).array; assert(take5 == take1); assert(take6 == take2); } }
May 15 2016
parent reply Basile B. <b2.temp gmx.com> writes:
On Sunday, 15 May 2016 at 13:26:52 UTC, Joseph Rushton Wakeling 
wrote:
 On Sunday, 15 May 2016 at 11:15:38 UTC, Joseph Rushton Wakeling 
 wrote:
 On Sunday, 15 May 2016 at 10:43:55 UTC, Joseph Rushton 
 Wakeling wrote:
 Probably the best way to handle this is to handle the 
 take-the-address side of things by a  trusted wrapper that 
 uses `return ref` to guarantee the pointer remains valid for 
 the lifetime of the wrapper itself.
Note, I've been mulling over this myself for a while, so I'll probably put something together in a future dxorshift release (and probably try to get it in Phobos ASAP, as it will be very helpful in avoiding the worst cases of the existing RNG functionality).
Sneak preview to try out, before I tidy this up for actual inclusion in the library (needs docs, etc):
The wrapper could be smaller with an alias this: ---- public struct SafeUniformRNG (BaseRNG) if (isUniformRNG!BaseRNG) { public: this (return ref BaseRNG generator) trusted { this.gen = &generator; } enum isUniformRandom = BaseRNG.isUniformRandom; ref BaseRNG getGen() { return *gen; } alias getGen this; private: BaseRNG* gen; invariant() { assert(this.gen !is null); } } ---- even if I'm not 100% sure if this is conform with previous version. At least the tests pass.
May 15 2016
parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On Sunday, 15 May 2016 at 14:25:44 UTC, Basile B. wrote:
 The wrapper could be smaller with an alias this:

 [... snip ...]

 even if I'm not 100% sure if this is conform with previous 
 version. At least the tests pass.
I'm surprised that one passes the test, static assert(!isForwardRange!SafeRNG); ... ? Or did you only try the tests applied to the dxorshift generators? More generally: what I'd be worried about with this version is that it readily re-opens the door to accidentally copying the underlying RNG by value, if (as with Phobos RNGs) the postblit is not disabled. The wrapper I provided is more verbose, but it should guarantee statistical safety in that respect. I also have a personal bugbear about `alias this` inasmuch as the current permissions constraints _force_ the exposure of implementation details (i.e. the `getGen` method has to be public), but that's more of a frustration than a serious worry in this case ;-)
May 15 2016
parent reply Basile B. <b2.temp gmx.com> writes:
On Sunday, 15 May 2016 at 14:49:16 UTC, Joseph Rushton Wakeling 
wrote:
 On Sunday, 15 May 2016 at 14:25:44 UTC, Basile B. wrote:
 The wrapper could be smaller with an alias this:

 [... snip ...]

 even if I'm not 100% sure if this is conform with previous 
 version. At least the tests pass.
I'm surprised that one passes the test, static assert(!isForwardRange!SafeRNG); ... ? Or did you only try the tests applied to the dxorshift generators?
I confirm that all of them are run. As in your original paste. All pass, 100% coverage. No problem. Anyway, NVM I should just take care of my own buisness...
May 15 2016
parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On Sunday, 15 May 2016 at 15:15:30 UTC, Basile B. wrote:
 I confirm that all of them are run. As in your original paste. 
 All pass, 100% coverage. No problem. Anyway, NVM I should just 
 take care of my own buisness...
Ah, interesting. I think you may have discovered a bug in `isForwardRange`, because that test _should_ have detected that, if BaseRNG is a forward range, the RNG accessed via `alias this` is also `save`able. static assert(!is(typeof(SafeRNG.save))); ... works, however. Thank you very much for the suggestions here -- you showed up a nasty hole in the existing tests.
May 15 2016
next sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On Sunday, 15 May 2016 at 15:33:24 UTC, Joseph Rushton Wakeling 
wrote:
 I think you may have discovered a bug in `isForwardRange`
Less a bug than a subtlety, it seems. Because of this line: https://github.com/dlang/phobos/blob/778593d805a0c8bf39e318163e6d4004a7357904/std/range/primitives.d#L790 ... the wrapper using `alias this` doesn't count as a forward range, because the result of `.save` is of the same type as the underlying RNG, rather than the wrapper itself. The `.save` method still exists, though, although it's probably unlikely to be used in practice because `isForwardRange` evaluates to false.
May 15 2016
prev sibling parent ag0aep6g <anonymous example.com> writes:
On 05/15/2016 05:33 PM, Joseph Rushton Wakeling wrote:
 Ah, interesting.  I think you may have discovered a bug in
 `isForwardRange`, because that test _should_ have detected that, if
 BaseRNG is a forward range, the RNG accessed via `alias this` is also
 `save`able.
For a forward range, save must return the very same type. A forwarded `save` returns a different type.
May 15 2016
prev sibling parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On Sunday, 15 May 2016 at 11:15:38 UTC, Joseph Rushton Wakeling 
wrote:
 On Sunday, 15 May 2016 at 10:43:55 UTC, Joseph Rushton Wakeling 
 wrote:
 Probably the best way to handle this is to handle the 
 take-the-address side of things by a  trusted wrapper that 
 uses `return ref` to guarantee the pointer remains valid for 
 the lifetime of the wrapper itself.
Note, I've been mulling over this myself for a while, so I'll probably put something together in a future dxorshift release (and probably try to get it in Phobos ASAP, as it will be very helpful in avoiding the worst cases of the existing RNG functionality).
Wrapper implemented here, together with documentation and tests: https://github.com/WebDrake/dxorshift/pull/1 N.B. I'm sticking with the explicit wrapper, because I want to be really, really certain that what comes out is an input range whose underling RNG can _never_ be copied by value.
May 15 2016
parent reply jmh530 <john.michael.hall gmail.com> writes:
On Sunday, 15 May 2016 at 23:34:46 UTC, Joseph Rushton Wakeling 
wrote:
 Wrapper implemented here, together with documentation and tests:
 https://github.com/WebDrake/dxorshift/pull/1

 N.B. I'm sticking with the explicit wrapper, because I want to 
 be really, really certain that what comes out is an input range 
 whose underling RNG can _never_ be copied by value.
Thought you might find this interesting: http://news.utexas.edu/2016/05/16/computer-science-advance-could-improve-cybersecurity and reddit discussion: https://www.reddit.com/r/technology/comments/4jvihm/computer_scientists_have_developed_a_new_method/
May 18 2016
next sibling parent Kagamin <spam here.lot> writes:
On Wednesday, 18 May 2016 at 16:12:35 UTC, jmh530 wrote:
 Thought you might find this interesting:
 http://news.utexas.edu/2016/05/16/computer-science-advance-could-improve-cybersecurity

 and reddit discussion:
 https://www.reddit.com/r/technology/comments/4jvihm/computer_scientists_have_developed_a_new_method/
That's more or less what random.org does.
May 18 2016
prev sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On Wednesday, 18 May 2016 at 16:12:35 UTC, jmh530 wrote:
 On Sunday, 15 May 2016 at 23:34:46 UTC, Joseph Rushton Wakeling 
 wrote:
 Wrapper implemented here, together with documentation and 
 tests:
 https://github.com/WebDrake/dxorshift/pull/1

 N.B. I'm sticking with the explicit wrapper, because I want to 
 be really, really certain that what comes out is an input 
 range whose underling RNG can _never_ be copied by value.
Thought you might find this interesting: http://news.utexas.edu/2016/05/16/computer-science-advance-could-improve-cybersecurity and reddit discussion: https://www.reddit.com/r/technology/comments/4jvihm/computer_scientists_have_developed_a_new_method/
Yea, I was looking at that earlier today -- looks interesting! It would be good to try to implement it for D.
May 18 2016