## double puzzle: the next floor

2008-06-03

As I was looking at ms I came across some C code of the form:

`floor(1 + x) - 1`

where x is a double precision floating point value. (I’m too polite to show you the actual code, see streec.c line 443 if you must).

Question: when is this different from `floor(x)`?

It’s quite a fun little puzzle. I give my answers below.

For the purposes of this discussion I’ll assume that `double` is an IEEE double precision floating point type. So that means `double` exactly represents numbers of the form

m×2e

where m and e are both integers, respecting the following ranges:
-253 < m < 253
-1074 <= e <= 971

253 is the first value that occurred to me. This is the smallest integer representable as a double where its successor is not exactly representable. So if x is 253 then x+1 is also 253 (IEEE round-to-even), floor(253) is 253 (it’s an integer), and 253 – 1 is exactly representable (the successor of 253 is not exactly representable, but its predecessor is).

A similar thing happens for some of the numbers bigger than 253 and less than 254. In this range the step between adjacent doubles is 2 (in the representation scheme above, e is 1). These doubles are all integers, so `floor` isn’t going to change anything, so `floor(1+x)-1)` is `(x+1)-1`, and `floor(x)` is `x`. When x is a double represented by an m that is odd then x+1 and x will be different because of the round-to-even rule. For exactly the same reason x+1-1 will be the same as x+1. An example is x = 253+2. This is represented as 4503599627370497×21, but x+1-1 is 4503599627370498×21. In general a similar thing happens for a number of the form 2i where i is an odd positive integer and 252 < i < 253.

The previous problem was that we had a number x and adding 1 to it made the result round up to the next higher integer. A similar thing happens for very small negative values. If x is negative and very close to 0 then x+1 might be sufficiently close to 1 to be rounded to 1. This happens when -2-54 <= x < 0 (numbers just a bit less than -2-54 get round to 1-2-53 when 1 is added to them).

-0. This is sort of degenerate case of the above. -0 can be thought of as being just the tiniest bit less than 0, and this difference cancels completely when 1 is added.

In the above case when x is small and negative what happens is that it is just smaller than an integer, and this difference gets cancelled entirely when 1 is added. So that whilst x is not an integer x+1 is. A similar thing happens at every number that’s just a bit less than an integer power of 2 (a reasonably small positive power of 2). For example 7.999999999999999 (which is 8-2-50) rounds to 9 when 1 is added. So `floor(7.999999999999999+1)-1` is 8, but floor(7.999999999999999) is 7. This happens for every number of the form 2i-2i-53 (this is nextafter(2i, 0)) where i is a non-negative integer and i < 52.

Possibly I’ve missed some cases. Especially negative ones.

In the case where I originally found the code I’m pretty sure the difference is irrelevant.

### 2 Responses to “double puzzle: the next floor”

1. kallum Says:

booring

2. drj11 Says:

noted.