www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Different random shuffles generated when compiled with gdc than with

reply "Andrew Brown" <aabrown24 hotmail.com> writes:
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
next sibling parent reply "Wanderer" <no-reply no-reply.org> writes:
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
parent "Andrew Brown" <aabrown24 hotmail.com> writes:
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
prev sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
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.

 ...

 Andrew


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.
May 30 2014
next sibling parent reply "Andrew Brown" <aabrown24 hotmail.com> writes:
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.

 ...

 Andrew


 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.
May 30 2014
parent reply Russel Winder via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
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
parent "Dicebot" <public dicebot.lv> writes:
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:

 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?


There is currently no GDC version with same frontend as latest 
DMD relese.
May 30 2014
prev sibling parent reply Joseph Rushton Wakeling via Digitalmars-d-learn writes:
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
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
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:

 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.


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.
May 30 2014
next sibling parent "Andrew Brown" <aabrown24 hotmail.com> writes:
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:

 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.


 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.
May 31 2014
prev sibling next sibling parent Joseph Rushton Wakeling via Digitalmars-d-learn writes:
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
prev sibling next sibling parent reply Joseph Rushton Wakeling via Digitalmars-d-learn writes:
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:

 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.


 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.


It's due to the the updated uniform() provided in this pull request:
https://github.com/D-Programming-Language/phobos/commit/fc48d56284f19bf171780554b63b4ae83808b894
May 31 2014
parent reply "Ivan Kazmenko" <gassa mail.ru> writes:
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:

 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.


 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.


 It's due to the the updated uniform() provided in this pull 
 request:
 https://github.com/D-Programming-Language/phobos/commit/fc48d56284f19bf171780554b63b4ae83808b894


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.org
Jun 01 2014
next sibling parent "Andrew Brown" <aabrown24 hotmail.com> writes:
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:

 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.


 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.


 It's due to the the updated uniform() provided in this pull 
 request:
 https://github.com/D-Programming-Language/phobos/commit/fc48d56284f19bf171780554b63b4ae83808b894


 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.org
Jun 01 2014
prev sibling next sibling parent reply Joseph Rushton Wakeling via Digitalmars-d-learn writes:
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
parent reply "Chris Cain" <zshazz gmail.com> writes:
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
parent reply Joseph Rushton Wakeling via Digitalmars-d-learn writes:
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 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.


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.
Jun 02 2014
parent "Chris Cain" <zshazz gmail.com> writes:
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
prev sibling next sibling parent "Andrew Brown" <aabrown24 hotmail.com> writes:
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
prev sibling parent "Kagamin" <spam here.lot> writes:
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
prev sibling parent Joseph Rushton Wakeling via Digitalmars-d-learn writes:
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/fc48d56284f19bf171780554b63b4ae83808b894


You 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