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.

About these ads

2 Responses to “double puzzle: the next floor”

  1. kallum Says:

    booring


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: