Issue 67 in ardb: Patch: use std::random_shuffle for draw simulator shuffle

[codesite...@google.com]

Status: New
Owner: ----

New issue 67 by meteor...@yahoo.com.au: Patch: use std::random_shuffle for
draw simulator shuffle
http://code.google.com/p/ardb/issues/detail?id=67

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

Attachments:
shuffle.patch 4.5 KB

--
You received this message because you are listed in the owner
or CC fields of this issue, or because you starred this issue.
You may adjust your issue notification preferences at:
http://code.google.com/hosting/settings

--
You received this message because you are subscribed to the Google Groups "ardb-devel" group.
To post to this group, send email to ardb-...@googlegroups.com.
To unsubscribe from this group, send email to ardb-devel+...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/ardb-devel?hl=en.

[codesite...@google.com]

Comment #1 on issue 67 by meteor...@yahoo.com.au: Patch: use

std::random_shuffle for draw simulator shuffle
http://code.google.com/p/ardb/issues/detail?id=67

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

[codesite...@google.com]

Comment #2 on issue 67 by graham.r.smith: Patch: use std::random_shuffle

for draw simulator shuffle
http://code.google.com/p/ardb/issues/detail?id=67

Thank you for this.

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

Graham.

[codesite...@google.com]

Updates:
Status: Fixed

Comment #3 on issue 67 by Woodruffr1973: Patch: use std::random_shuffle for

draw simulator shuffle
http://code.google.com/p/ardb/issues/detail?id=67

(No comment was entered for this change.)