Tuesday, July 15, 2008

1015 + 6 = 1000000000000005.9

In a prior entry we saw how the internal representation of numbers in Google Docs spreadsheets as double precision IEEE 754 floating point quantities introduces rounding errors when the stored values get larger than 253. Yet, this does not explain the fact that 19! is displayed as 121645100408831984, since 19!=121645100408832000 can be represented exactly in double precision IEEE 754.

Let us see how numbers are rounded in the vicinity of 121645100408832000:

Each number on the left column is the least value that gets rounded off to the associated number on the right column: for instance, the numbers 1216···1945 ≤ n ≤ 1216···1959 get mapped to 1216···1952, and so on. Except for the rows in bold, each rounding interval is comprised of 17 or 15 numbers (instead of each interval being of length 16, due to the application of unbiased rounding) around its central value. This is entirely reasonable because 19! is 57 bits wide and double precision IEEE 754 can only represent up to 53 significant bits, hence the hops of size 257−53 = 16. On the other hand, we have an anomaly between rows 4 and 5: the values from 1216···1992 to 1216···2008, which should map to 1216···2000, are instead rounded off to the preceding value 1216···1984.

The binary representation of 19! has 57 bits: if we divide by 16 we get the 53 bit wide number 7602818775552000, which ought be exactly representable in double precision IEEE 754. Pasting this into a Google Docs spreadsheet gets us:

which is off by one! If we keep dropping least significant bits from this number (i.e. dividing by 2) we obtain this:

Only the last number is shown correctly, but after that the display is correct all the way down to zero. This suggests that there is a lower limit below which we do not have displaying problems. After probing the number space more or less thoroughly, our findings are the following:

The problems occur from 1015 up. Displaying errors are extremely frequent and distributed very evenly: if we consider the sequence of exactly representable integers greater than 1015, roughly 11% of them are displayed incorrectly, with a typical distance between consecutive errors of 9, ocasionally a little more. The magnitud of the error is ~n/253. The smallest number displayed incorrectly is 1015 + 6 = 1000000000000006, which Google Docs spreadsheets show as 1000000000000005.9.

The problem seems to be related only to the displaying algorithm; numbers are stored correctly, as suggested by the following:

No comments:

Post a Comment