The trouble with `floor` and `ceil`

floor and ceil have the bad habit of producing unexpected results. They aren’t broken, but in light of floating point nasties can often result in a number that’s ±1 of the desired result.

Why it happens

By example, floor can take a value that is effectively 18 and convert it to 17. Consider this python example:

1
2
3
4
5

import math

a = 17.99999999999
print a
print math.floor(a)

On my computer this outputs:

1
2

18.0
17.0

In other languages, with different formatters, we can take off several 9’s from a and still get the same output. It depends on how the floating point formatter rounds the result. Unless we’ve given a format specifier that preserves the exact value (which is almost never the default), the above can happen.

Despite a value of 18.0 being printed floorstill lowers the value to 17. This is correct since technically a is less than 18, but rarely the behaviour we actually want.

The point here is not to say the formatting is wrong, but just to point out a potential trouble point. Consider in this case that while a ~= parse(format(a)), with a small tolerance, it is not true floor(a) ~= floor(parse(format(a)) — it’s off by a large amount. The result is very different depending how we’ve handled the input value.

Floating point precision always produces results that can vary slightly. Normally these variations aren’t relevant, but floor can magnify the slightest inaccuracy into a very large difference.

Always add a range

In Fuse this problem comes up in a few locations, one of which is the layout code. To provide visual crispness, locations and sizes are snapped to exact pixels. Positions are rounded to the nearest value and the size is always rounded up.

A lot of calculations are involved in calculating a size; the precise floating point value that comes out can vary up/down slightly. For most values this isn’t an issue, but for a size hovering around an integer it can be. Two items that are logically the same size might end up with differing sizes of 17.999 and 18.001 pixels. It would be somewhat distracting if one ended up a full pixel larger on the display.

To get a reasonable ceil behaviour we subtract an epsilon:

1
2
3
4
5

const float pixelEpsilon = 0.005f;

float SnapSize(float p) {
    return Math.Ceil(p - pixelEpilson);
}

This results in any value up to 18.005 being snapped to 18, preventing a value like 18.001 from snapping to 19.

The epsilon of 0.005 was determined to be a good value for this domain. It is intended only as a safeguard against floating point inaccuracy. Anything higher and we’d start breaking the layout rule that sizes are rounded up. In our clipping code, which decides what to draw to the screen, the epsilon is a bit larger. That’s based on the assumption that something covering only a tiny fraction of a pixel will have no actual visual effects.

floor can be modified in the same way by adding the epsilon value:

1
2
3

float SnapDown(float p) {
    return Math.Floor(p + pixelEpsilon);
}

Update: Round-trip idempotence

The above examples are just to show the core concept and I admit don’t completely illustrate the problem. In Fuse we store positions and sizes in “device independent pixels”, called “points”. To do pixel snapping I might first convert to pixel space, round the value, and then convert back. That gives me this function (with the epsilon):

1
2
3
4
5

float SnapSize( float pts ) {
    var px = ConvertPointsToPixels(pts);
    px = Math.Ceil( px - pixelEpsilon );
    return ConvertPixelsToPoints(px);
}

Without a pixelEpsilon this function is not idempotent: SnapSize(x) != SnapSize(SnapSize(x)). floor itself is idempotent, but the precision of the conversion functions introduces a slight inaccuracy. The pixel cannot be represented exactly in point space, and thus when I convert back to pixels I may get a value slightly more than a full integer. Calling Ceil on this would then bump the number up again.

For our code it was important that this function is idempotent as it is called at various times during layout, and during layout animation between frames.

Think before you floating point

As with all things floating point, studious attention to the algorithm is required. We can’t just blindly use the floor and ceil functions and get the desired results. Including an epsilon in the calculation ensures that close-to-integer values remain at that integer.