random number [0, 99]
in [C++]
|
From: Pete Becker on 10 Feb 2006 21:30 kevin.hall(a)motioneng.com wrote: >>Which C library is "the C library"? > > > Ok, you're right here. What I should have said to be more clear is > "Many implementations of the C library use 'simple' PNRGs that are > notorious for this behavior. What you've said is quite clear. Your basis for saying it is not. Which simple implementations are notorious for this behavior? Which C libraries use these simple implementations? > In particular, many older libraries use > linear congruential generators which are known to display this > behavior". Which libraries are those, and which ones are still in use? -- 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: kevin.hall on 11 Feb 2006 06:18 > You must qualify your assertion to modulo a power of 2. Those are > the only ones where the high order bits have no contribution. No, the assertion is still true. You are right that modulos of numbers that are not a power of two do have all bits contribute. But they do not all contribute equally. This is easily demonstrated: Take the following extreme example. The highest bit is random. All other bits are non-random. The nth random number is: Rn = n + <random bit>*(1<<30) Then we choose our modulo to be something close to a power of two. Say 8193. Here's an example output: 1073741825 => 17 (after mod 8193) 1073741826 => 18 3 => 3 4 => 4 1073741829 => 21 1073741830 => 22 1073741831 => 23 8 => 8 1073741833 => 25 1073741834 => 26 11 => 11 12 => 12 13 => 13 14 => 14 1073741839 => 31 16 => 16 1073741841 => 33 18 => 18 1073741843 => 35 1073741844 => 36 21 => 21 1073741846 => 38 1073741847 => 39 24 => 24 25 => 25 26 => 26 1073741851 => 43 1073741852 => 44 1073741853 => 45 1073741854 => 46 1073741855 => 47 Not very random! (If you keep generating more numbers, you'll see a definite linear pattern). Anyway, I know this is an extreme example, but it does illustrate a point. In a modulo -- even with a number that's not a power of two -- the lower bits have a greater significance. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Carlos Moreno on 11 Feb 2006 06:27 kanze wrote: > Still, if you have an application where you must have a certain > quality generator, you have to provide your own; the C++ > standard doesn't give any guarantee. I don't mean to jump in sounding like a suck-up (:-)), but I do believe this is really the most relevant and most precise aspect mentioned so far in the thread. My initial take was based on the premise that rand() was to be used, and that that part was not necessarily an option. Under that premise, my take is that using modulo *could* introduce a particular problem in some situations, whereas division does not introduce that problem, or any other obvious problem (notice that there is emphasis on whether the operation -- modulo or division -- *introduces* an additional problem, in addition to any problems already present in the given PRNG). For that reason, I defend the idea of choosing division up front, without asking too many questions (in that situation, of course). Of course, I can't remember the last time I used rand(), or even the rand48 family :-) Cheers, Carlos -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Martin Eisenberg on 11 Feb 2006 12:18 kevin.hall(a)motioneng.com wrote: > 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. http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/efaq.html says: "In the rare case that the rounding-off error becomes a problem, obtain minimum integer n such that N<=2^n, generate integer random numbers, take the most significant n bits, and discard those more than or equal to N." Note the penultimate part. Whether that's grounded in any way or just erring on the safe side, the authors are probably in the best position to tell you. Martin -- Quidquid latine scriptum sit, altum viditur. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Seungbeom Kim on 13 Feb 2006 04:55
Francis Glassborow wrote: > > 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. I have to agree strongly. The pair of rand() and RAND_MAX is so primitive, and puts the same kind of arithmetic burden over and over upon the shoulders of those programmers who need random numbers in a specific range. It is further justified by the fact that the value of rand() is pretty useless unless it's further conditioned to fall into a specific range; we'd never use the value directly, which means *every* user of rand() would be doing the same thing manually. Shouldn't we have in the standard library something like nrand(n) which returns a random number in the range [0, n)? Of course we do have Boost.Random, but since it's much more complex and it has a much steeper learning curve, I think it's better to leave it for more serious tasks and let simpler tasks take advantage of rand() more easily. -- Seungbeom Kim [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |