[Math] Calculate the total number of floating-point numbers in a certain range

arithmeticcomputer sciencefloating point

This was inspired by this Stack Overflow question.

It's currently on hold as off-topic and downvoted, so just in case it's deleted here's the screenshot (for us lesser mortals with less than 10K rep on that site):
enter image description here

The program is trying to list all of the double values between these two numbers:

0.009999999999999999999999999999
0.099999999999999999999999999999

The code in the screenshot won't actually do that, but let's leave that aside for now.

For those who are unfamiliar with the C# type system, a double is a floating-point number (which is used to represent real numbers) with the following attributes:

The Double value type represents a double-precision 64-bit number with values ranging from negative 1.79769313486232e308 to positive 1.79769313486232e308, as well as positive or negative zero, PositiveInfinity, NegativeInfinity, and not a number (NaN). It is intended to represent values that are extremely large (such as distances between planets or galaxies) or extremely small (the molecular mass of a substance in kilograms) and that often are imprecise (such as the distance from earth to another solar system). The Double type complies with the IEC 60559:1989 (IEEE 754) standard for binary floating-point arithmetic.

Now obviously there are an infinite number of real numbers between these values, but only a finite number of floating point numbers (since any number in an actual computer can obviously only have a finite number of digits).

The other thing to understand is Double.Epsilon, which is the following constant:

The value of the Epsilon property reflects the smallest positive Double value that is significant in numeric operations or comparisons when the value of the Double instance is zero…

More precisely, the floating point format consists of a sign, a 52-bit mantissa or significand, and an 11-bit exponent. As the following example shows, zero has an exponent of -1022 and a mantissa of 0. Epsilon has an exponent of -1022 and a mantissa of 1. This means that Epsilon is the smallest positive Double value greater than zero and represents the smallest possible value and the smallest possible increment for a Double whose exponent is -1022.

My question, then: how many double numbers are there between 0.009999999999999999999999999999 and 0.099999999999999999999999999999?

If I'm correct, I believe that asking how many numbers are between 0.009999999999999999999999999999 and 0.099999999999999999999999999999 is exactly the same as asking how many numbers there are between 0.0 and 0.09 (which is also considerably more convenient to read and work with).

As an experiment, I tried the following program to get a better sense of the size of the number (never expecting it to actually complete execution):

double num = 0.0;
long count = 0;

// Loop through all of the double numbers from 0.0 to 0.09
while (num <= 0.09)
{
    // Add the smallest possible increment
    num += Double.Epsilon;

    // Keep count of how many there are
    count++;
}

// Print the number at the end
Console.WriteLine(count);

I paused the program after letting it run for awhile; current number was 1.86324012918674E-314 and the count was 3,771,240,006.

I strongly suspect that you could either do some form of arithmetic on the exponents or possibly set this up as a permutation of some kind; is there an equation that can describe this problem?

Best Answer

You have to look at the structure of how a floating point number is stored. In IEEE 754 a 64 bit float is defined to have a sign bit $S$, $11$ bits of exponent $E$, and $53$ bits of mantissa $M$. The first bit of the mantissa is always $1$ and not stored, so only $52$ bits are stored. The value is $(-1)^S \cdot 2^{E-1023}\cdot M$ where $M$ is in binary with the radix point after the first (unstored) bit. This gives that there are $2^{52}$ values of $M$, so for each value of exponent we get $2^{52}$ floating point numbers.

To count the numbers between $n_1=0.009999999999999999999999999999$ and $n_2= 0.099999999999999999999999999999$ we first count the full steps of the exponent, then handle the partial steps at the end. $n_1 \lt 2^{-6}=0.015625$ and $n_2\gt 2^{-4}=0.0625$ so we get $3 \cdot 2^{52}$ numbers there. In the step where the exponent part is $2^{-7}$ the $\epsilon$ is $2^{-59}$ so there are $2^{59}(0.015625-n_1)=3242591731706757$. In the step where the exponent is $2^{-3}$ the $\epsilon$ is $2^{-55}$, so there are $2^{55}(n_2-0.0625)=13510798882111487$. If my copy and paste skills are working the total is $30264189495929732$ I think the rounding is correct. I don't care to try to list them all. It is definitely not the same as from $0$ to $0.09$ because that has over $1000$ steps of a factor two, so over $1000 \cdot 2^{52}$ numbers. In floating point the numbers are very dense near zero. You are adding a span near zero, so adding lots of numbers and not deleting nearly as many since the deleted span is "far from zero".

If you have the right tool available, you could just get the binary representation of $n_1$ and $n_2$ and subtract them. As the floating point representations are ordered the same way the corresponding values are, that will give you the count. Remember to subtract one because you shouldn't count either end.

Related Question