C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  random number [0, 99] Goto page 1, 2, 3  Next          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Guest Posted: Wed Feb 08, 2006 12:00 pm    Post subject: random number [0, 99] Hi, I am using the int version of rand() with MS Visual Studio. I would like to generate random number in the range of [0, 99]. Right now I am using rand() * 100 / (RAN_MAX + 1) I found that I got too much 0. 0 appears more than any other numbers. How can I fix it? Thanks, qq [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ulrich Eckhardt Guest Posted: Wed Feb 08, 2006 3:00 pm    Post subject: Re: random number [0, 99] quickcur (AT) yahoo (DOT) com wrote: Quote: Hi, I am using the int version of rand() with MS Visual Studio. I would like to generate random number in the range of [0, 99]. Right now I am using rand() * 100 / (RAN_MAX + 1) I found that I got too much 0. 0 appears more than any other numbers. How can I fix it? Several things on aove code: - RAND_MAX not RAN_MAX - RAND_MAX+1 might overflow - rand()*100 might overflow, too The easiest way is to call rand() until it gives a number in your range, obviously, but this could mean many calls. 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. The reason is easy: Assume RAND_MAX=9, i.e. rand() gives you numbers from 0 to 9. If you need numbers in the range 0 to 3, the following mapping applies: 0 -> 0 1 -> 1 2 -> 2 3 -> 3 4 -> 0 5 -> 1 6 -> 2 7 -> 3 8 -> reroll 9 -> reroll Uli [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Carlos Moreno Guest Posted: Wed Feb 08, 2006 3:00 pm    Post subject: Re: random number [0, 99] quickcur (AT) yahoo (DOT) com wrote: Quote: Hi, I am using the int version of rand() with MS Visual Studio. I would like to generate random number in the range of [0, 99]. Right now I am using rand() * 100 / (RAN_MAX + 1) I found that I got too much 0. 0 appears more than any other numbers. How can I fix it? Integer division. Plus, try a Google search on this newsgroup for plenty of discussions on *the* right way to do what you're trying to do (even if based on rand(), which is a poor RNG to begin with) -- I'm talking about discarding random numbers above the highest multiple of your number (100 in this case). HTH, Carlos -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Thomas Maeder Guest Posted: Wed Feb 08, 2006 3:00 pm    Post subject: Re: random number [0, 99] quickcur (AT) yahoo (DOT) com writes: Quote: Hi, I am using the int version of rand() with MS Visual Studio. I would like to generate random number in the range of [0, 99]. Right now I am using rand() * 100 / (RAN_MAX + 1) I found that I got too much 0. 0 appears more than any other numbers. How can I fix it? Learn how integer arithmetics works in C++. The expression rand()*100 may cause an overflow, resulting in a number below RAND_MAX. Dividing that number by RAND_MAX+1 will always give 0. A naive, but better approach is int randValue_0_100(std::rand()%100); This will produce numbers in the range 0..99, but the lower numbers will occur slightly more often because RAND_MAX typically isn't a multiple of 100. To fix for that, something like int const upper_rand_limit(RAND_MAX/100*100); int randValue; do { randValue = std::rand(); } while (randValue>=upper_rand_limit); int randValue_0_100(randValue%100); should work. To be really sure about the quality of your pseudo-random numbers, you have to carefully look at how it's documented and/or implemented, of course. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Maxim Yegorushkin Guest Posted: Wed Feb 08, 2006 6:00 pm    Post subject: Re: random number [0, 99] quickcur (AT) yahoo (DOT) com wrote: Quote: Hi, I am using the int version of rand() with MS Visual Studio. I would like to generate random number in the range of [0, 99]. Right now I am using rand() * 100 / (RAN_MAX + 1) I found that I got too much 0. 0 appears more than any other numbers. How can I fix it? (unsigned)rand() % 100; [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Guest Posted: Thu Feb 09, 2006 10:06 am    Post subject: Re: random number [0, 99] Modulo is a poor operation in helping find a random number. The reason is that the lowest bits in a psuedo-random number are less random than the upper bits. It's much better to use division: In the example above, the range [0,3] contains 4 numbers. [0,9] contains 10. 10/4 = 2 (integer division). 4*2 = 8 --> valid range for not rerolling must have 8 numbers: [0,7]. This is the same as above. But this time, rather than using modulo, integer divide by 2 (the result of 10/4): 0 -> 0 1 -> 0 2 -> 1 3 -> 1 4 -> 2 5 -> 2 6 -> 3 7 -> 3 8 -> reroll 9 -> reroll [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Maxim Yegorushkin Guest Posted: Thu Feb 09, 2006 3:06 pm    Post subject: Re: random number [0, 99] kevin.hall (AT) motioneng (DOT) com wrote: Quote: Modulo is a poor operation in helping find a random number. The reason is that the lowest bits in a psuedo-random number are less random than the upper bits. Are you talking about a specific implementation or does this behavior apply to any implementation of rand()? [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Carlos Moreno Guest Posted: Thu Feb 09, 2006 3:06 pm    Post subject: Re: random number [0, 99] Ulrich Eckhardt wrote: Quote: Several things on aove code: - RAND_MAX not RAN_MAX - RAND_MAX+1 might overflow - rand()*100 might overflow, too The easiest way is to call rand() until it gives a number in your range, obviously, but this could mean many calls. 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 -- in the case you describe, integer division works perfectly fine, and gives you a perfectly uniform distribution (i.e., it introduces no "disuniformities" in the distribution, with respect to the base RNG -- if rand() is perfectly uniform, then drawing numbers until you get one below the highest multiple of your range, then dividing by the right number would give you a perfectly uniform distribution in the given range) Quote: The reason is easy: Assume RAND_MAX=9, i.e. rand() gives you numbers from 0 to 9. If you need numbers in the range 0 to 3, 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 HTH, Carlos -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Pete Becker Guest Posted: Thu Feb 09, 2006 3:06 pm    Post subject: Re: random number [0, 99] kevin.hall (AT) motioneng (DOT) com wrote: Quote: Modulo is a poor operation in helping find a random number. The reason is that the lowest bits in a psuedo-random number are less random than the upper bits. That's a claim that's been made about certain types of random number generators. It's not universally true, nor even as broadly true as many people seem to believe. Quote: It's much better to use division: In the example above, the range [0,3] contains 4 numbers. [0,9] contains 10. 10/4 = 2 (integer division). 4*2 = 8 --> valid range for not rerolling must have 8 numbers: [0,7]. This is the same as above. No, it addresses a different, real, problem. When you try to put ten things into four slots, some slots will get more things than others. Translation: if the size of your target range doesn't exactly divide the size of your generator's range, you're going to get a less than perfect distribution, regardless of the quality of your generator. [good example snipped] -- 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! ] Back to top kanze Guest Posted: Thu Feb 09, 2006 3:06 pm    Post subject: Re: random number [0, 99] kevin.hall (AT) motioneng (DOT) com wrote: Quote: Modulo is a poor operation in helping find a random number. The reason is that the lowest bits in a psuedo-random number are less random than the upper bits. If that's the case, then it isn't a very good random number generator, right? Your statement is false for the random number generators I use. -- James Kanze GABI Software Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ulrich Eckhardt Guest Posted: Thu Feb 09, 2006 7:06 pm    Post subject: Re: random number [0, 99] Carlos Moreno wrote: Quote: 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 -- in the case you describe, integer division works perfectly fine, and gives you a perfectly uniform distribution (i.e., it introduces no "disuniformities" in the distribution, with respect to the base RNG -- if rand() is perfectly uniform, then drawing numbers until you get one below the highest multiple of your range, then dividing by the right number would give you a perfectly uniform distribution in the given range) I don't get you. I for sure did not say to use 'rand()%max_value', which introduces these uneven distributions and is therefore wrong - although I would like to amend that the nonuniformity is a function of max_value and RAND_MAX, for small max_values this might be good enough. Quote: The reason is easy: Assume RAND_MAX=9, i.e. rand() gives you numbers from 0 to 9. If you need numbers in the range 0 to 3, 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 Assuming rand() is evenly distributed, both mappings are equivalent, or am I missing something? Uli [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Guest Posted: Fri Feb 10, 2006 2:06 am    Post subject: Re: random number [0, 99] What denotes a good random number generator? No PSEUDO-random number generator is good compared to a TRUE random number generator. But the C library rand() (which Ulrich Eckhardt and others in this thread have recommended) is usually implemented as a linear congruential PRNG. And these are notorious for having less random lower order bits. What PRNG do you use? I use the mersenne-twister for anything that really matters in my work. 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. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Guest Posted: Fri Feb 10, 2006 2:06 am    Post subject: Re: random number [0, 99] Quote: It's not universally true, nor even as broadly true as many people seem to believe. Ok, fine. But again, the C library implementation of rand() is notorious for this behavior -- and that is what people in this thread are recommending. Perhaps not all rand() implementations are bad -- but some certainly are. Anyway, it seems that many people are fighting to defend their practice of using modulo. Division uses higher order bits which should be the most random in all good PRNGs. Modulo uses the lowest order bits which is known to NOT be very random in some cases. So which is better practice for general programming? Quote: No, it addresses a different, real, problem. I should have been more clear. I understand that some slots in general will get more hits than others. I was trying to address the problem from a different perspective. In my example, I ended up with 8 valid slots (just like Ulrich's example) and that is what I meant by "This is the same as above". Does this make sense? [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Thomas Maeder Guest Posted: Fri Feb 10, 2006 3:06 am    Post subject: Re: random number [0, 99] Carlos Moreno <moreno_at_mochima_dot_com (AT) mailinator (DOT) com> writes: Quote: 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 http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Francis Glassborow Guest Posted: Fri Feb 10, 2006 3:06 am    Post subject: Re: random number [0, 99] In article <1139433651.899829.311980 (AT) g47g2000cwa (DOT) googlegroups.com>, kevin.hall (AT) motioneng (DOT) com writes Quote: Modulo is a poor operation in helping find a random number. The reason is that the lowest bits in a psuedo-random number are less random than the upper bits. It's much better to use division: And that is completely irrelevant even if it were true (which it generally isn't) unless you are dividing by a power of two. However this is definitely wandering far from the subject matter for this newsgroup. However I see so many requests for functionality to select at random one element from a range that I begin to wonder if we should not have a standard library function template that simply returns a random member from a container. We could then apply it to an array of int when we wanted to select an integer value from a small range. -- Francis Glassborow ACCU Author of 'You Can Do It!' see http://www.spellen.org/youcandoit For project ideas and contributions: http://www.spellen.org/youcandoit/projects [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Goto page 1, 2, 3  Next Page 1 of 3   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.