A caution about ceil

The ceiling function of x, ⌈x⌉, is defined as the lowest integer at least x, or “x rounded up” as people might say. People often think of it as the next integer after x, but this is a subtle mistake. Although that’s true when x is a fraction, it’s not true when x is an integer! Integers are fixed points under ceil, which is often unintended.

In my experience, what’s usually desired instead of ⌈x⌉ is ⌊x⌋ + 1, or equivalently ⌊x + 1⌋. The two functions are mostly the same, but unlike ⌈x⌉, ⌊x⌋ + 1 is never equal to x. Programmers make this mistake so often that it’s worth habitually checking for whenever you see the ceiling function (and, to a lesser extent, the floor function) in a program. Typically, it suffices to check a single case where the argument to the ceiling is an integer.

An example application where this arises is when answering the question “How many digits are in the number x?” Let’s say our base is 10 and x is 1234. Taking the logarithm gives 3.0913. Clearly, the integer answer we’re after is the integer after 3, so we’re tempted to conclude the formula to be used is ⌈log x⌉. But this fails us when the logarithm is an integer, such as when x = 1000. Note that 1000 is a four-digit number, even though its logarithm is three, and the ceiling function doesn’t change 3 into 4. Instead, use ⌊x⌋ + 1.


Posted

in

by

Tags: