default random object?

[Steve Schveighoffer]

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
>>> <schveiguy at 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