0
votes

This is more a curiosity than a technical problem.

I'm trying to better understand how floating point numbers are handled in Python. In particular, I'm curious about the number returned by sys.float_info.epsilon = 2.220446049250313e-16. I can see, looking up on the documentation on Double-precision floating-point, that this number can also be written as 1/pow(2, 52). So far, so good.

I decided to write a small python script (see below. Disclaimer: this code is ugly and can burn your eyes) which start from eps = 0.1 and makes the comparison 1.0 == 1.0 + eps. If False, it means eps is big enough to make a difference. Then I try to find a smaller number by subtracting 1 from the last digit and adding the digit 1 to the right of the last and looking for False again by incrementing the last digit.

I am pretty confident that the code is ok because at certain point (32 decimal places) I get eps = 0.00000000000000011102230246251567 = 1.1102230246251567e-16 which is very close to 1/pow(2, 53) = 1.1102230246251565e-16 (last digit differs by 2).

I thought the code would no produce sensible numbers after that. However, the script kept working, always zeroing in a more accurate decimal number until it reached 107 decimal places. Beyond that, the code did not find a False to the test. I got very intrigued with that result and could not wrap my head around it.

Does this 107 decimal places float number have any meaning? If positive, what is it particular about it? If not, what is python doing past the 32 decimal places eps? Surely there is some algorithm python is cranking to get to the 107 long float.

The script.

total = 520 # hard-coded after try-and-error max number of iterations.
dig = [1]
n = 1
for t in range(total):
    eps = '0.'+''.join(str(x) for x in dig)
    if(1.0 == 1.0 + float(eps)):
        if dig[-1] == 9:
            print(eps, n)
            n += 1
            dig.append(1)
        else:
            dig[-1] += 1
    else:
        print(eps, n)
        n += 1
        dig[-1] -= 1
        dig.append(1)

The output (part of it). Values are the eps and the number of decimal places

0.1 1
0.01 2
(...)
0.000000000000001 15
0.0000000000000002 16
0.00000000000000012 17
0.000000000000000112 18
0.0000000000000001111 19
0.00000000000000011103 20
(...)
0.0000000000000001110223024625157 31
0.00000000000000011102230246251567 32
0.000000000000000111022302462515667 33
(...)
0.000000000000000111022302462515666368314810887391490808258832543534838643850548578484449535608291625976563 105
0.0000000000000001110223024625156663683148108873914908082588325435348386438505485784844495356082916259765626 106
0.00000000000000011102230246251566636831481088739149080825883254353483864385054857848444953560829162597656251 107

I ran this code in Python 3.8.3 (tags/v3.8.3:6f8c832, May 13 2020, 22:20:19) [MSC v.1925 32 bit (Intel)] on win32.

1
A double precision normalized floating point number is uniquely determined by giving it with 17 decimals. So, after 1.1102230246251566e-16 all the numbers you are getting will produce the same float. - NotDijkstra
A good read. See also the sentence after the proof of Theorem 15. - NotDijkstra
Is your question why python prints out such long floats? - Ann Zen
No. My question is about the meaning of numbers past 32 decimal places. - Alexandre de Castro Maciel
@NotDijkstra.I tried two tests with numbers 1 digit longer than the limit you have mentioned: 1.0 == 1.0 + 0.000000000000000111022302462515667 returns False and 1.0 == 1.0 + 0.000000000000000111022302462515666 returns True. I assume this indicates they are different floats. Is that a correct assumption? - Alexandre de Castro Maciel

1 Answers

1
votes

Your test involves a double rounding and is finding the number 2−53+2−105.

Many Python implementations use the IEEE-754 binary64 format. (This is not required by the Python documentation.) In this format, the significand (fraction portion) of a floating-point number has 53 bits. (52 are encoded in a primary significand field. 1 is encoded via the exponent field.) For numbers in the interval [1, 2), the significand is scaled (by the exponent portion of the floating-point representation) so that its leading bit corresponds to a value of 1 (20). This means is trailing bit corresponds to a value of 2−52.

Thus, the difference between 1 and the next number representable in this format is 2−52—that is the smallest change that can be made in the number, by increasing the low bit.

Now, suppose x contains 1. If we add 2−52 to it, we will of course get 1+2−52, since that result is representable. What happens if we add something slightly smaller, say ¾•2−52? In this case, the real-number result, 1+¾•2−52, is not representable. It must be rounded to a representable number. The common default rounding method is to round to the nearest representable number. In this case, that is 1+2−52.

Thus, adding to 1 some numbers smaller than 2−52 still produces 1+2−52. What is the smallest number we can add to 1 and get this result?

In case of ties, where the real-number result is exactly halfway between two representable numbers, the common default rounding method uses the one with the even low bit. So, with a choice between 1 (trailing bit 0) and 1+2−52 (trailing bit 1), it chooses 1. That means if we add ½•2−52 to 1, it will produce 1.

If we add any number greater than ½•2−52 to 1, there will be no tie; the real-number result will be nearer to 1+2−52, and that will be the result.

The next question is what is the smallest number greater than ½•2−52 (2−53) that we can add to 1? If the number has to be in the IEEE-754 binary64 format, it is limited by its significand. With the leading bit scaled to represent 2−53, the trailing bit represents 2−53−52 = 2−105.

Therefore, 2−53+2−105 is the smallest binary64 value we can add to 1 to get 1+2−52.

As your program tests values, it works with a decimal numeral. That decimal numeral is converted to the floating-point format and then added to 1. So it is finding the smallest number in the floating-point format that produces a sum greater than 1, and that is the number described above, 2−53+2−105. Its value in decimal is 1.110223024625156663683148108873914908082588325435348386438505485784844495356082916259765625•10−16.