digitalmars.D.learn - Different random shuffles generated when compiled with gdc than with
- Andrew Brown (24/24) May 30 2014 Hi there,
- Wanderer (8/8) May 30 2014 I must note if the sequence is predictable, it's not random
- Andrew Brown (13/21) May 30 2014 I'd like it to be predictable given the seed, right now it's
- monarch_dodra (4/20) May 30 2014 Are you sure you are compiling with the same version of dmd and
- Andrew Brown (5/32) May 30 2014 GDC version 4.8.2,i guess that's my problem. This is what happens
- Russel Winder via Digitalmars-d-learn (9/11) May 30 2014 Debian Sid has GCC 4.9 packages, but that may not help?
- Dicebot (4/11) May 30 2014 There is currently no GDC version with same frontend as latest
- Joseph Rushton Wakeling via Digitalmars-d-learn (3/6) May 30 2014 Which fixes are you thinking of here ... ? I don't recall anything that...
- monarch_dodra (5/14) May 30 2014 Didn't you make changes to how and when the global PRNG is popped
- Andrew Brown (4/19) May 31 2014 Looking at old data, it is the dmd version that's changed, so I
- Joseph Rushton Wakeling via Digitalmars-d-learn (11/13) May 31 2014 No, it was partialShuffle that I tweaked, and that shouldn't affect the ...
- Joseph Rushton Wakeling via Digitalmars-d-learn (3/9) May 31 2014 It's due to the the updated uniform() provided in this pull request:
- Ivan Kazmenko (21/36) Jun 01 2014 I second the thought that reproducibility across different
- Andrew Brown (5/44) Jun 01 2014 Thank you for hunting down the difference, in my case it's not a
- Joseph Rushton Wakeling via Digitalmars-d-learn (7/15) Jun 01 2014 Yes, there probably should be a high bar for changes that break reproduc...
- Chris Cain (8/12) Jun 01 2014 To clarify, no, the uniform was not ported from Java's Random.
- Joseph Rushton Wakeling via Digitalmars-d-learn (5/11) Jun 02 2014 I'm really sorry, Chris, I was obviously mixing things up: on rereading,...
- Chris Cain (11/16) Jun 02 2014 It's cool. :)
- Andrew Brown (3/3) Jun 02 2014 Having read more of the debate, I think coverage is more
- Kagamin (3/9) Jun 02 2014 It can be done by using standardized algorithms like one in FIPS
- Joseph Rushton Wakeling via Digitalmars-d-learn (12/14) May 31 2014 You can see the effects in action by running e.g. the following D code:
Hi there, The following code: void main(){ import std.array : array; import std.stdio : writeln; import std.random : rndGen, randomShuffle; import std.range : iota; rndGen.seed(12); int[] temp = iota(10).array; randomShuffle(temp); writeln(temp); } writes [1, 8, 4, 2, 0, 7, 5, 6, 9, 3] if it's compiled with dmd, but [1, 7, 4, 6, 2, 9, 5, 0, 3, 8] with gdc. I'd like to allow the users to specify an integer if they wish to give a deterministic set of permutations. This won't matter if I only distribute a binary created with a given compiler (aside from scaring me into thinking I need to know more about random number generation), but it's an annoyance when I'm trying to check my code is doing what it should. Is there a better way to specify an integer seed so both compilers will agree on the permutations they generate? Thanks very much Andrew
May 30 2014
I must note if the sequence is predictable, it's not random anymore, it's pseudo-random at most. Also, if anyone interested, PHP had such way to generate predictable sequences in the past, but after it was horribly misused by various people for crypto keys/password generation purposes, they have forbidden it completely, so only non-predictable sequences in PHP from now on. Maybe, just maybe, it makes sense not to stand on the same rack twice.
May 30 2014
I'd like it to be predictable given the seed, right now it's predictable given the seed and the compiler. Is this a bug, shouldn't the random number process be completely defined in the language? I'm not trying to misuse it like the PHP crowd :) It's for a piece of scientific software: I'm hoping people will test the significance of their results with a stochastic process, and for reproducibility we need to allow other people to recreate their analysis exactly (hence the seed). For my purposes I don't need truly random, I just need it not to repeat too quickly. Thanks Andrew On Friday, 30 May 2014 at 14:09:20 UTC, Wanderer wrote:I must note if the sequence is predictable, it's not random anymore, it's pseudo-random at most. Also, if anyone interested, PHP had such way to generate predictable sequences in the past, but after it was horribly misused by various people for crypto keys/password generation purposes, they have forbidden it completely, so only non-predictable sequences in PHP from now on. Maybe, just maybe, it makes sense not to stand on the same rack twice.
May 30 2014
On Friday, 30 May 2014 at 13:39:18 UTC, Andrew Brown wrote:Hi there, The following code: void main(){ import std.array : array; import std.stdio : writeln; import std.random : rndGen, randomShuffle; import std.range : iota; rndGen.seed(12); int[] temp = iota(10).array; randomShuffle(temp); writeln(temp); } writes [1, 8, 4, 2, 0, 7, 5, 6, 9, 3] if it's compiled with dmd, but [1, 7, 4, 6, 2, 9, 5, 0, 3, 8] with gdc. ... AndrewAre you sure you are compiling with the same version of dmd and gdc? Fixes were made to the rand.d library in the latest release, which could explain the difference you are observing.
May 30 2014
GDC version 4.8.2,i guess that's my problem. This is what happens when you let Ubuntu look after your packages. Thank you very much! Andrew On Friday, 30 May 2014 at 16:13:49 UTC, monarch_dodra wrote:On Friday, 30 May 2014 at 13:39:18 UTC, Andrew Brown wrote:Hi there, The following code: void main(){ import std.array : array; import std.stdio : writeln; import std.random : rndGen, randomShuffle; import std.range : iota; rndGen.seed(12); int[] temp = iota(10).array; randomShuffle(temp); writeln(temp); } writes [1, 8, 4, 2, 0, 7, 5, 6, 9, 3] if it's compiled with dmd, but [1, 7, 4, 6, 2, 9, 5, 0, 3, 8] with gdc. ... AndrewAre you sure you are compiling with the same version of dmd and gdc? Fixes were made to the rand.d library in the latest release, which could explain the difference you are observing.
May 30 2014
On Fri, 2014-05-30 at 16:44 +0000, Andrew Brown via Digitalmars-d-learn wrote:GDC version 4.8.2,i guess that's my problem. This is what happens when you let Ubuntu look after your packages.Debian Sid has GCC 4.9 packages, but that may not help? -- Russel. ============================================================================= Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.net 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
May 30 2014
On Saturday, 31 May 2014 at 06:54:13 UTC, Russel Winder via Digitalmars-d-learn wrote:On Fri, 2014-05-30 at 16:44 +0000, Andrew Brown via Digitalmars-d-learn wrote:There is currently no GDC version with same frontend as latest DMD relese.GDC version 4.8.2,i guess that's my problem. This is what happens when you let Ubuntu look after your packages.Debian Sid has GCC 4.9 packages, but that may not help?
May 30 2014
On 30/05/14 18:13, monarch_dodra via Digitalmars-d-learn wrote:Are you sure you are compiling with the same version of dmd and gdc? Fixes were made to the rand.d library in the latest release, which could explain the difference you are observing.Which fixes are you thinking of here ... ? I don't recall anything that ought to alter the behaviour of the standard random number generator.
May 30 2014
On Friday, 30 May 2014 at 18:41:55 UTC, Joseph Rushton Wakeling via Digitalmars-d-learn wrote:On 30/05/14 18:13, monarch_dodra via Digitalmars-d-learn wrote:Didn't you make changes to how and when the global PRNG is popped and accessed in randomShuffle? I figured it *could* be an explanation.Are you sure you are compiling with the same version of dmd and gdc? Fixes were made to the rand.d library in the latest release, which could explain the difference you are observing.Which fixes are you thinking of here ... ? I don't recall anything that ought to alter the behaviour of the standard random number generator.
May 30 2014
Looking at old data, it is the dmd version that's changed, so I think this is the likely reason. Andrew On Friday, 30 May 2014 at 20:45:23 UTC, monarch_dodra wrote:On Friday, 30 May 2014 at 18:41:55 UTC, Joseph Rushton Wakeling via Digitalmars-d-learn wrote:On 30/05/14 18:13, monarch_dodra via Digitalmars-d-learn wrote:Didn't you make changes to how and when the global PRNG is popped and accessed in randomShuffle? I figured it *could* be an explanation.Are you sure you are compiling with the same version of dmd and gdc? Fixes were made to the rand.d library in the latest release, which could explain the difference you are observing.Which fixes are you thinking of here ... ? I don't recall anything that ought to alter the behaviour of the standard random number generator.
May 31 2014
On 30/05/14 22:45, monarch_dodra via Digitalmars-d-learn wrote:Didn't you make changes to how and when the global PRNG is popped and accessed in randomShuffle? I figured it *could* be an explanation.No, it was partialShuffle that I tweaked, and that shouldn't affect the results here. There was a bug where partialShuffle would _always_ shuffle the whole of the input; but that wouldn't affect the results of randomShuffle itself, which calls partialShuffle with the explicit request to shuffle the entire array. Just to be sure I checked with random/partialShuffle pre- and post- my patches, and the result is identical: [1, 8, 4, 2, 0, 7, 5, 6, 9, 3] just as the OP gets for dmd. I think it's more likely that the culprit is either your set of patches to the Mersenne Twister, or the patches made to uniform() (which is called by partialShuffle). I'll look more deeply into this.
May 31 2014
On 31/05/14 22:37, Joseph Rushton Wakeling via Digitalmars-d-learn wrote:On 30/05/14 22:45, monarch_dodra via Digitalmars-d-learn wrote:It's due to the the updated uniform() provided in this pull request: https://github.com/D-Programming-Language/phobos/commit/fc48d56284f19bf171780554b63b4ae83808b894Didn't you make changes to how and when the global PRNG is popped and accessed in randomShuffle? I figured it *could* be an explanation.I think it's more likely that the culprit is either your set of patches to the Mersenne Twister, or the patches made to uniform() (which is called by partialShuffle). I'll look more deeply into this.
May 31 2014
On Saturday, 31 May 2014 at 21:22:48 UTC, Joseph Rushton Wakeling via Digitalmars-d-learn wrote:On 31/05/14 22:37, Joseph Rushton Wakeling via Digitalmars-d-learn wrote:I second the thought that reproducibility across different versions is an important feature of any random generation library. Sadly, I didn't use a language yet which supported such a flavor of reproducibility for a significant period of time in its default random library, so I have to use my own randomness routines when it matters. I've reported my concern [1] at the moment of breakage, but apparently it didn't convince people. Perhaps I should make a more significant effort next time (like a pull request) for the things that matter to me. Well, now I know it does matter for others, at least. In short, if uniform() has to be tweaked, the sooner it happens, the better. Alternatively, the library design could allow different uniform() implementations to be plugged in, and provide legacy implementations along with the current (default) one. In that case, all one has to do to reproduce the old behavior is to plug the appropriate one in. [1] http://forum.dlang.org/thread/vgmdoyyqhcqurpmobyuy forum.dlang.org#post-gjuprkxzmcbdixtbucea:40forum.dlang.orgOn 30/05/14 22:45, monarch_dodra via Digitalmars-d-learn wrote:It's due to the the updated uniform() provided in this pull request: https://github.com/D-Programming-Language/phobos/commit/fc48d56284f19bf171780554b63b4ae83808b894Didn't you make changes to how and when the global PRNG is popped and accessed in randomShuffle? I figured it *could* be an explanation.I think it's more likely that the culprit is either your set of patches to the Mersenne Twister, or the patches made to uniform() (which is called by partialShuffle). I'll look more deeply into this.
Jun 01 2014
Thank you for hunting down the difference, in my case it's not a deal breaking problem. I can just specify the compiler and language version, then the results become reproducible. And I'm sure I'll appreciate the performance boost! On Sunday, 1 June 2014 at 12:11:22 UTC, Ivan Kazmenko wrote:On Saturday, 31 May 2014 at 21:22:48 UTC, Joseph Rushton Wakeling via Digitalmars-d-learn wrote:On 31/05/14 22:37, Joseph Rushton Wakeling via Digitalmars-d-learn wrote:I second the thought that reproducibility across different versions is an important feature of any random generation library. Sadly, I didn't use a language yet which supported such a flavor of reproducibility for a significant period of time in its default random library, so I have to use my own randomness routines when it matters. I've reported my concern [1] at the moment of breakage, but apparently it didn't convince people. Perhaps I should make a more significant effort next time (like a pull request) for the things that matter to me. Well, now I know it does matter for others, at least. In short, if uniform() has to be tweaked, the sooner it happens, the better. Alternatively, the library design could allow different uniform() implementations to be plugged in, and provide legacy implementations along with the current (default) one. In that case, all one has to do to reproduce the old behavior is to plug the appropriate one in. [1] http://forum.dlang.org/thread/vgmdoyyqhcqurpmobyuy forum.dlang.org#post-gjuprkxzmcbdixtbucea:40forum.dlang.orgOn 30/05/14 22:45, monarch_dodra via Digitalmars-d-learn wrote:It's due to the the updated uniform() provided in this pull request: https://github.com/D-Programming-Language/phobos/commit/fc48d56284f19bf171780554b63b4ae83808b894Didn't you make changes to how and when the global PRNG is popped and accessed in randomShuffle? I figured it *could* be an explanation.I think it's more likely that the culprit is either your set of patches to the Mersenne Twister, or the patches made to uniform() (which is called by partialShuffle). I'll look more deeply into this.
Jun 01 2014
On 01/06/14 14:11, Ivan Kazmenko via Digitalmars-d-learn wrote:I second the thought that reproducibility across different versions is an important feature of any random generation library. Sadly, I didn't use a language yet which supported such a flavor of reproducibility for a significant period of time in its default random library, so I have to use my own randomness routines when it matters. I've reported my concern [1] at the moment of breakage, but apparently it didn't convince people. Perhaps I should make a more significant effort next time (like a pull request) for the things that matter to me. Well, now I know it does matter for others, at least.Yes, there probably should be a high bar for changes that break reproducibility in this way (although there certainly shouldn't be a ban: we shouldn't artificially constrain ourselves to avoid significant improvements to the module). I missed the debate at the time, but actually, I'm slightly more concerned over the remark in that discussion that the new uniform was ported from java.util.Random. Isn't OpenJDK GPL-licensed ... ?
Jun 01 2014
On Sunday, 1 June 2014 at 14:22:31 UTC, Joseph Rushton Wakeling via Digitalmars-d-learn wrote:I missed the debate at the time, but actually, I'm slightly more concerned over the remark in that discussion that the new uniform was ported from java.util.Random. Isn't OpenJDK GPL-licensed ... ?To clarify, no, the uniform was not ported from Java's Random. The comment in question: https://github.com/D-Programming-Language/phobos/pull/1717#issuecomment-29712117 It was found after the code was made. It's more-or-less the same approach (so, it gives credit to the mathematical soundness) but it was discovered independently.
Jun 01 2014
On 02/06/14 08:57, Chris Cain via Digitalmars-d-learn wrote:On Sunday, 1 June 2014 at 14:22:31 UTC, Joseph Rushton Wakeling via Digitalmars-d-learn wrote:I'm really sorry, Chris, I was obviously mixing things up: on rereading, the person in the earlier forum discussion (not PR thread) who talks about porting from Java wasn't you. I'm very glad to be corrected on that; your PR was a nice submission and I'm glad we have it in Phobos.I missed the debate at the time, but actually, I'm slightly more concerned over the remark in that discussion that the new uniform was ported from java.util.Random. Isn't OpenJDK GPL-licensed ... ?To clarify, no, the uniform was not ported from Java's Random.
Jun 02 2014
On Monday, 2 June 2014 at 18:46:18 UTC, Joseph Rushton Wakeling via Digitalmars-d-learn wrote:I'm really sorry, Chris, I was obviously mixing things up: on rereading, the person in the earlier forum discussion (not PR thread) who talks about porting from Java wasn't you. I'm very glad to be corrected on that; your PR was a nice submission and I'm glad we have it in Phobos.It's cool. :) I enjoyed making the contribution and hope I can make more in the future (but I've been pretty busy recently and I don't want to do anything if I can't guarantee follow ups). I want to say that I really appreciate your work on D's random generation as well. It gets a lot more attention than most languages'. I really hate when languages completely neglect it and have highly vulnerable random number generation that everyone uses because they assume it works well.
Jun 02 2014
Having read more of the debate, I think coverage is more important than reproducibility. From my point of view, I'm not sure if there's much point in giving reproducible wrong answers.
Jun 02 2014
On Sunday, 1 June 2014 at 12:11:22 UTC, Ivan Kazmenko wrote:I second the thought that reproducibility across different versions is an important feature of any random generation library. Sadly, I didn't use a language yet which supported such a flavor of reproducibility for a significant period of time in its default random library, so I have to use my own randomness routines when it matters.It can be done by using standardized algorithms like one in FIPS 186-2. Because it's standardized, it can't be improved.
Jun 02 2014
On 31/05/14 23:22, Joseph Rushton Wakeling via Digitalmars-d-learn wrote:It's due to the the updated uniform() provided in this pull request: https://github.com/D-Programming-Language/phobos/commit/fc48d56284f19bf171780554b63b4ae83808b894You can see the effects in action by running e.g. the following D code: //-------------------------------------------------------------- import std.algorithm, std.random, std.range, std.stdio; void main() { rndGen.seed(12); iota(0, 10).map!(a => uniform(0, 10 - a, rndGen)).writeln; } //-------------------------------------------------------------- ... which corresponds to the underlying calls to uniform() found in the shuffle process.
May 31 2014