Discrete distribution of numbers in binary?

Question

I heard somewhere that there are more numbers between .9 and 1 than between 0 and .1, when representing them as discrete finite bits (let's assume 32-bit floats for sake of argument). Can someone explain to me why this is the case and give an example of a number between 0 and .1 that can't be represented but its corresponding number between .9 and 1 (found by mathematically adding .9) can be represented by a float?

(This is relevant to rngs because they may be biased toward different ranges.)

Answer 1

The basic reason why your reasoning is wrong is that adding 0.9 is not an invertable operation. However you have it backwards. There are more floating point numbers between 0.0 and 0.1 than between 0.9 and 1.0.

As for how to make an unbiased floating point RNG, you should initially generate numbers in the range [1.0,2.0) then translate and scale the result accordingly. This works because the interval [1.0,2.0) has uniform precision across the entire range (the exponent is the same for all numbers in this range).

If you're working with IEEE single precision, which has the form:

s eeeeeeee mmmmmmmmmmmmmmmmmmmmmmm

Just fix the sign and exponent bits, and use a uniform random PRNG for integers to fill the mantissa bits. The same would apply to double.

Answer 2

The reason that there are more floating point numbers in the range 0.0 0.1 than between 0.9 1.0 (not the reverse) is easy to grap, once you understand that a floating point number uses a fixed amount of binary digits for the mantissa and the rest for the scale. Imagine, for the sake of illustration, that we store decimal digits instead of binary digits (the principle is the same), and assume that we have only 2 digits for the mantissa. Then, say, using the mantisa "57" we can represent a lot of numbers in the interval [0 0.1): 0.057 0.0057 0.00057 ... (as many as the scale digits allow us), and so on. But for the interval [0.9 1) we are extremely restricted: actually we have only 10 values (mantissa "9x", one single scale).

give an example of a number between 0 and .1 that can't be represented but its corresponding number between .9 and 1 (found by mathematically adding .9) can be represented by a float?

(Actually the situation is the reverse). Take the example above (two decimal digits for the mantissa) the number 0.0057 is representable, while 0.9057 is not.