Proper way to generate a random float given a binary random number generator?

Question

Let's say we have a binary random number generator, int r(); that will return a zero or a one both with propability 0.5.

I looked at Boost.Random, and they generate, say, 32 bits and do something like this (pseudocode):

x = double(rand_int32());
return min + x / (2^32) * (max - min);

I have some serious doubts about this. A double has 53 bits of mantissa, and 32 bits can never properly generate a fully random mantissa, among other things such as rounding errors, etc.

What would be a fast way to create a uniformly distributed float or double in the half-open range [min, max), assuming IEEE754? The emphasis here lies on correctness of distribution, not speed.

To properly define correct, the correct distribution would be equal to the one that we would get if we would take an infinitely precise uniformly distributed random number generator and for each number we would round to the nearest IEEE754 representation, if that representation would still be within [min, max), otherwise the number would not count for the distribution.

P.S.: I would be interested in correct solutions for open ranges as well.

Answer 1

AFAIK, the correct (and probably also fastest) way is to first create a 64 bit unsigned integer where the 52 fraction bits are random bits, and the exponent is 1023, which if type punned into a (IEEE 754) double will be a uniformly distributed random value in the range [1.0, 2.0). So the last step is to subtract 1.0 from that, resulting in a uniformly distributed random double value in the range [0.0, 1.0).

In pseudo code:

rndDouble = bitCastUInt64ToDouble(1023 << 52 | rndUInt64 & 0xfffffffffffff) - 1.0

This method is mentioned here: http://xoroshiro.di.unimi.it (See "Generating uniform doubles in the unit interval")

EDIT: The recommended method has since changed to: (x >> 11) * (1. / (UINT64_C(1) << 53))

See above link for details.