News for hackers. Stuff that matters.
Re:State of the art of random double generation by SamReidHughes on Friday April 10, 2015 @06:06AM (#9353380)
This 1:2:1 distribution is the right sort of behavior for a double-precision random number generator (what the standard says notwithstanding). It's what you get if you throw a uniform random dart at the real line and round it to the nearest floating point number.

Also, a <= x <= b is really the right way for uniform floating point ranges to be, with half-probability of the edges getting selected. The API of returning [0, 1) is pretty horrid, because then when somebody uses that to generate [1, 2), by doing rand01() + 1.0, they actually create the possibility of generating 2, because (1-2^-53) + 1 rounds up to 2. (That's just like the rounding that happens when generating to [2^52, 2^52+2].)

If you want a <= x < b, getting that for practical purposes could be relatively simple: compute rand01() * (b - a) + a, and if the output is >= b, then return a. That works wonderfully if rand01() behaves like randint(2^53) / 2.0^53. It's a little suboptimal if rand01() is implemented something like randint(2^64) / 2.0^64, because it creates a weird little density spike at the bottom for contrived ranges such as [2.0^-30, 1 + 2.0^-30), but if you're getting that anal you'd also worry about the round-to-even behavior of computing rand01() + 1.0.

Re:State of the art of random double generation by Someone on Friday April 10, 2015 @07:27AM (#9353607)
"It's what you get if you throw a uniform random dart at the real line and round it to the nearest floating point number."

Only when you throw the dart, repeat until you are in the target interval, and then look for the nearest representable number. If you throw the dart, look for the nearest representable number and repeat until that number is in the interval, you get something different.

Worse, neither approach gives you a uniform distribution in the general case. The hypothetical uniform dart is as likely to land between 1 and 2 as it is to land between 2 and 3, but there are more representable numbers in the first range than in the second.

I also think your rand01() + 1.0 example is flawed. It is just because floating point is hard that this kind of functionality ends up in a standard library.

Re:State of the art of random double generation by SamReidHughes on Friday April 10, 2015 @02:59PM (#9356417)
> Only when you throw the dart, repeat until you are in the target interval, and then look for the nearest representable number.

Yeah, when you throw your dart at the target interval.

> If you throw the dart, look for the nearest representable number and repeat until that number is in the interval, you get something different.

I don't know why you'd want to throw a uniform dart at some other, larger interval, before culling it down. You can't throw a uniform random dart at the entire real line. I think what you're describing gives undue representation to the edges -- you wouldn't use those sampling points with those weightings to integrate a function, but you might use the trapezoid method.

> The hypothetical uniform dart is as likely to land between 1 and 2 as it is to land between 2 and 3, but there are more representable numbers in the first range than in the second.

That's a fact of life.