Patch: use std::random_shuffle for draw simulator shuffle

[GoogleCodeExporter]

Hi Devs,

Firstly, thanks for the great tool.

I was checking out the source code to drawsimulator.cpp and noticed that
the shuffling algorithm can be both optimised and simplified by just
calling std::random_shuffle. I've attached a patch against the latest SVN
version (241) [patch metrics: 32 lines removed, 17 lines added].

Beyond the code simplification there are a couple of extra reasons to use
std::random_shuffle:

* Although I think the existing shuffling algorithm is correct, the
random_shuffle algorithm has been proven to be correct (it is an
implementation of 3.4.2 of Knuth [D. E. Knuth, The Art of Computer
Programming. Volume 2: Seminumerical Algorithms, second edition.
Addison-Wesley, 1981]).

* I suspect there is actually a minor error with the current ardb shuffle.
Not in the shuffling method but in the random integer generation used in
the shuffle; namely in the function DrawSimulator::Random (int iMax):

Currently it is:
int DrawSimulator::Random(int iMax) {
  return (int)(iMax*(rand()*1.0)/RAND_MAX);
}

I think it should be:
int DrawSimulator::Random(int iMax) {
  return (int)(iMax*((double)rand()/((double)RAND_MAX+(double)(1))));
}

See http://members.cox.net/srice1/random/crandom.html on why this is a less
unbiased method of obtaining an integer in the range [0, iMax).

Note: the attached patch removes DrawSimulator::Random altogether, so this
is probably a moot issue anyway.

Feel free to do whatever you want with the patch and keep up the great work!

Cheers,
Ivor Blockley

Original issue reported on code.google.com by meteor...@yahoo.com.au on 18 Apr 2010 at 7:57

Attachments:

• shuffle.patch

[GoogleCodeExporter]

Minor correction:
Replace "less unbiased" with "less biased" in the original bug report (around 
line 32).

Original comment by meteor...@yahoo.com.au on 18 Apr 2010 at 8:01

[GoogleCodeExporter]

Thank you for this.

When I find some dev time I will merge this patch in and test it.

Graham.

Original comment by graham.r...@gmail.com on 19 Apr 2010 at 9:23

[GoogleCodeExporter]

Original comment by Woodruffr1973@gmail.com on 13 Dec 2010 at 9:41

• Changed state: Fixed