digitalmars.D.announce - dxorshift: random number generators from the extended Xorshift family
- Joseph Rushton Wakeling (42/42) May 15 2016 http://code.dlang.org/packages/dxorshift
- Basile B. (10/24) May 15 2016 Nice,
- Joseph Rushton Wakeling (15/22) May 15 2016 The @safe side of things is obviously a concern, but having @safe
- Joseph Rushton Wakeling (7/11) May 15 2016 Note, I've been mulling over this myself for a while, so I'll
- Joseph Rushton Wakeling (137/148) May 15 2016 Sneak preview to try out, before I tidy this up for actual
- Basile B. (28/44) May 15 2016 The wrapper could be smaller with an alias this:
- Joseph Rushton Wakeling (16/20) May 15 2016 I'm surprised that one passes the test,
- Basile B. (5/16) May 15 2016 I confirm that all of them are run. As in your original paste.
- Joseph Rushton Wakeling (9/12) May 15 2016 Ah, interesting. I think you may have discovered a bug in
- Joseph Rushton Wakeling (10/11) May 15 2016 Less a bug than a subtlety, it seems. Because of this line:
- ag0aep6g (3/7) May 15 2016 For a forward range, save must return the very same type. A forwarded
- Joseph Rushton Wakeling (7/18) May 15 2016 Wrapper implemented here, together with documentation and tests:
- jmh530 (6/11) May 18 2016 Thought you might find this interesting:
- Kagamin (2/6) May 18 2016 That's more or less what random.org does.
- Joseph Rushton Wakeling (3/17) May 18 2016 Yea, I was looking at that earlier today -- looks interesting!
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
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
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
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
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: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); } }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
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: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.On Sunday, 15 May 2016 at 10:43:55 UTC, Joseph Rushton Wakeling wrote:Sneak preview to try out, before I tidy this up for actual inclusion in the library (needs docs, etc):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
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
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: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...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?
May 15 2016
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
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
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
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: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.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
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
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
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:Yea, I was looking at that earlier today -- looks interesting! It would be good to try to implement it for D.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