Struct urandom::distributions::Float01
source · pub struct Float01;
Expand description
A distribution to sample floating point numbers uniformly in the open interval (0, 1)
, i.e. not including either endpoint.
Precision
This implementation does not suffer from bias in the low bits of the mantissa.
Implementation notes
The implementation is simple, fast and straighforward from the following observations:
Dividing a floating point number in half is exactly the same as subtracting one from its exponent. With a given exponent the mantissa provides all values between 2exp and 2exp+1.
Eg. With an exponent of -1
the resulting mantissa defines a floating point number in half-open interval [0.5, 1.0)
.
With an exponent of -2
the floating point number is in the half-open interval [0.25, 0.5)
and so on.
In a loop flip a coin, if heads produce a floating point number with the current exponent starting at -1
if tails subtract one from the exponent and repeat.
This produces smaller floating point numbers with exponentially less probability (of base 2) which is exactly what we want.
The loop can be avoided by generating a single u64
and looking at the individual bits, subtract one for every 0
bit until a 1
bit is encountered.
This operation is efficiently implemented in hardware known as the count leading zeros instruction (eg. LZCNT
in x86).
There is a small bias in case the Rng outputs all zeros but in practice this should never happen unless your PRNG is broken.
The result is two calls to the Rng, one for generating 64 bits worth of coin flips and one for generating the mantissa of the resulting float.