Steve Schveighoffer wrote:
On Mon, 16 Feb 2009 12:20:34 +0900, Bill Baxter wrote:
On Mon, Feb 16, 2009 at 12:07 PM, Steve Schveighoffer
<schvei...@yahoo.com> wrote:
On Sun, 15 Feb 2009 17:27:38 -0800, Andrei Alexandrescu wrote:
Ok. Let me just note that rand()%max is a lousy method of generating
random numbers between 0 and max-1 and everybody should put that in
the bin with Popular Examples That Should Never Be Used, together with
exponential Fibonacci, linear-space factorial, and bubblesort.
Do you mean rand()%max specifically in the case of the C function rand
()? Or using %max on any random number generator in general. If the
first case, I totally agree, and I found out that from experience
first, then googling second :) But if the latter, I wasn't aware that
all RNGs were bad at randomizing the lower bits, so could you explain
why?
It's also possible that Lionello meant the latter case as well.
It's bad in general. Say your RNG generates perfectly uniform numbers
between 0 and 10.
Now you say RNG()%7 to get values 0..6 Not all inputs map to outputs
evenly now. More inputs map to 0 than to 6, so the distribution is no
longer uniform.
Of course if you % by something that divides evenly into the RNG's range
then it shouldn't be a problem, other than the lack of randomness in
lower bits of some rand() implementations.
--bb
Hm... good point, but probably not significant unless you are generating
numbers in a range close to the maximum range. For example, the 0..6
range isn't going to divide evenly into int.max, but the bias towards
certain values is going to be very slight. I would guess then that the
correct method is to add n to the nth random number generated? Or is
there a better way?
See the implementation of uniform in std.random.
Andrei
