random number [0, 99]
in [C++]
|
From: Carlos Moreno on 9 Feb 2006 21:34 Ulrich Eckhardt wrote: >>>A more sophisticated way is to first determine the largest multiple of >>>your range that is smaller or equal to RAND_MAX, call rand() until the >>>value is >>>in that range and then simply apply the modulo operator to the result. >> >>NO!!!! >> >>Do *NOT* use modulo for this sort of things [...] > > I don't get you. *sigh* Join the club :-) > I for sure did not say to use 'rand()%max_value', which > introduces these uneven distributions and is therefore wrong Indeed. That would have been *severely* wrong. As pointed out already, the lower bits, for certain classes of generators and certain implementations tend to have lower "randomness" than the higher bits. rand() tends to be one of those implementations in which the above tends to be true. The argument of using division instead of modulo goes like this: if the RNG suffers from that defect [lower randomness in the lower bits], then division is ok and modulo is not. And if the RNG does not suffer at all from that defect, then both [division and modulo] are equally good. So, in some cases modulo is worse, and in no case division is worse -- why use modulo then? Carlos -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Ulrich Eckhardt on 10 Feb 2006 05:48 Carlos Moreno wrote: [using modulo versus using integer division to cut down an RNG's range] > As pointed out already, the lower bits, for certain classes of > generators and certain implementations tend to have lower > "randomness" than the higher bits. [snipped further explanation] > So, in some cases modulo is worse, and in no case division > is worse -- why use modulo then? Okay, now that's a reasoning I accept! However, I'd like to point out something: you implemented a workaround but omitted to document what exactly it was you were working around. As you already saw, someone else that read your code (in this case me) already nullified your fix because he didn't know what the counterintuitive code was supposed to fix. Yes, I also sometimes think that everybody should know this or that... Uli [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Pete Becker on 10 Feb 2006 05:57 Carlos Moreno wrote: > > rand() tends to be one of those implementations in which the > above tends to be true. > More accurately, it is frequently said that some implementations of rand() have that problem. -- Pete Becker Dinkumware, Ltd. (http://www.dinkumware.com) [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Carlos Moreno on 10 Feb 2006 05:56 Thomas Maeder wrote: >>>the following mapping applies: >>>0 -> 0 >>>1 -> 1 >>>2 -> 2 >>>3 -> 3 >>>4 -> 0 >>>5 -> 1 >>>6 -> 2 >>>7 -> 3 >>>8 -> reroll >>>9 -> reroll >> >>Good, except that it should be: >> >>0 -> 0 >>1 -> 0 >>2 -> 1 >>3 -> 1 >>4 -> 2 >>5 -> 2 >>6 -> 3 >>7 -> 3 >>8 -> reroll >>9 -> reroll > > > If the numbers 0 to 7 occur with equal probability, I don't see a > fundamental difference why your suggestion should be better. > > Care to elaborate? See my reply to Ulrich in a sibling sub-thread. Carlos -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Pete Becker on 10 Feb 2006 05:56
kevin.hall(a)motioneng.com wrote: > Though I believe the MT is less susceptible > to having lower order bits be less random, I haven't yet seen a study > that proves that. I would like to though -- seriously I would. If you > can point me to one or to a study that proves that the lower order bits > for the PRNGs that you use are not less random, please post a link. > Interesting: you ask for proof that other RNGs are good, but accept the mersenne twister on faith. -- Pete Becker Dinkumware, Ltd. (http://www.dinkumware.com) [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |