On Sun, 15 Feb 2009 20:30:06 -0800, Andrei Alexandrescu wrote: > 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
Ugh, so you have to repeatedly generate random numbers until it gives you a value inside your range? Using your calculation for bucketsize, if I want to generate a random number between 0 and (urng.max - urng.min) / 2 + 1 will enter a loop for which it throws away half the random numbers generated? It seems like there should be a better method, but I can't think of one right now. You also can add an optimization to your code, change your final code to: auto maxvalue = urng.min + myRange * bucketSize + (bucketSize - 1); do { r = urng.next; // avoid calculation in loop } while (r > maxvalue); return _a + (r - urng.min) / bucketSize; Not sure if it makes a huge difference, or has a huge negative impact when it's not important. -Steve