janmr blog

Useful Properties of the Floor and Ceil Functions

This articles explores some basic properties of the integer functions commonly known as floor and ceil. Most of the statements may seem trivial or obvious, but I, for one, have a tendency to forget just how exact you can be when it comes to expressions/equations where floor or ceil functions appear.

First, the definitions:

  • x=max{nZnx}\lfloor x \rfloor = \max \{ n \in \mathbb{Z} \mid n \leq x \} = the greatest integer less than or equal to xx,
  • x=min{nZnx}\lceil x \rceil = \min \{ n \in \mathbb{Z} \mid n \geq x \} = the least integer greater than or equal to xx,

for every real number xx.

Equality

What can we say about xx and nn if n=xn=\lfloor x \rfloor or n=xn=\lceil x \rceil? First of all, we obviously have n=xn = x if and only if xx is an integer. Let us now consider the floor function \lfloor \cdot \rfloor. With xx some real number we have xx\lfloor x \rfloor \leq x, easily seen from the definition. Now let n=xn=\lfloor x \rfloor and assume x1nx-1 \geq n which is equivalent to n+1xn+1 \leq x. But then nn cannot be the greatest integer less than or equal to xx so we have a contradiction. Since xx was chosen arbitrarily we have x1<xx-1 < \lfloor x \rfloor for all xx. Similar considerations can be made for the ceil function \lceil \cdot \rceil and we get the important inequalities:

x1  <  x    x    x  <  x+1.x-1 \;<\; \lfloor x \rfloor \;\leq\; x \;\leq\; \lceil x \rceil \;<\; x+1.

At the same time, we have the right-going implications of the following statements (xx is a real number and nn an integer):

n=xnx<n+1,n=xx1<nx,n=xn1<xn,n=xxn<x+1.\begin{aligned} n=\lfloor x \rfloor \quad &\Longleftrightarrow \quad n \leq x < n+1, \\ n=\lfloor x \rfloor \quad &\Longleftrightarrow \quad x-1 < n \leq x, \\ n=\lceil x \rceil \quad &\Longleftrightarrow \quad n-1 < x \leq n, \\ n=\lceil x \rceil \quad &\Longleftrightarrow \quad x \leq n < x+1. \\ \end{aligned}

Let us show the fourth left-going implication. Assume xn<x+1x \leq n < x+1 and set k=xk=\lceil x \rceil. We then have xk<x+1x \leq k < x+1 from which we get n<x+1k+1n < x+1 \leq k+1 and k<x+1n+1k < x+1 \leq n+1, so n=k=xn=k=\lceil x \rceil. The remaining three left-going implication can be proved in much the same way.

From the statements above we can show some useful equalities:

n=x    x1<nx    xn<x+1    n=x,n=\lfloor -x \rfloor \;\Leftrightarrow\; -x-1 < n \leq -x \;\Leftrightarrow\; x \leq -n < x+1 \;\Leftrightarrow\; -n=\lceil x \rceil,

so x=x\lfloor -x \rfloor = -\lceil x \rceil for all xx, and

xx<x+1    x+kx+k<x+k+1    x+k=x+k,\lfloor x \rfloor \leq x < \lfloor x \rfloor+1 \;\Leftrightarrow\; \lfloor x \rfloor + k \leq x+k < \lfloor x \rfloor + k+1 \;\Leftrightarrow\; \lfloor x \rfloor + k = \lfloor x+k \rfloor,

so x+k=x+k\lfloor x \rfloor + k = \lfloor x+k \rfloor for all integer kk. Naturally, the similar x+k=x+k\lceil x \rceil + k = \lceil x+k \rceil also holds.

Inequalities

We now consider what can be said when inequalities are involved. Let xx be some real number and nn an integer. We then have the following:

x<nx<n,n<xn<x,xnxn,nxnx.\begin{aligned} x < n \quad &\Longleftrightarrow \quad \lfloor x \rfloor < n, \\ n < x \quad &\Longleftrightarrow \quad n < \lceil x \rceil, \\ x \leq n \quad &\Longleftrightarrow \quad \lceil x \rceil \leq n, \\ n \leq x \quad &\Longleftrightarrow \quad n \leq \lfloor x \rfloor. \end{aligned}

All we need to show these are xx<x+1\lfloor x \rfloor \leq x < \lfloor x \rfloor + 1 and x1<xx\lceil x \rceil - 1 < x \leq \lceil x \rceil from the previous section, and the fact that n<m+1n < m+1 is equivalent to nmn \leq m when mm and nn are integers. Consider, for instance, the third statement from above. If xnx \leq n then we have x1<xn\lceil x \rceil - 1 < x \leq n, which implies xn\lceil x \rceil \leq n. On the other hand, if xn\lceil x \rceil \leq n then xnx \leq n because xxx \leq \lceil x \rceil. The remaining statements are shown in a similar manner.

Some Increasing Functions

Certain functions have special properties when used together with floor and ceil. Such a function f:RRf: \mathbb{R} \rightarrow \mathbb{R} must be continuous and monotonically increasing and whenever f(x)f(x) is integer we must have that xx is integer. An example could be f(x)=xf(x) = \sqrt{x}. Note that being continuous and monotonically increasing ensures a well-defined inverse f1f^{-1}. One of the requirements can then be formulated as f1(y)f^{-1}(y) must be integer for all integer yy.

Using the results of the previous sections we get

k=f(x)kf(x)<k+1f1(k)x<f1(k+1)f1(k)x<f1(k+1)kf(x)<k+1f(x)=k.\begin{aligned} k = \lfloor f( \lfloor x \rfloor ) \rfloor \quad &\Leftrightarrow \quad k \leq f(\lfloor x \rfloor) < k+1 \quad \Leftrightarrow \quad f^{-1}(k) \leq \lfloor x \rfloor < f^{-1}(k+1) \\ &\Leftrightarrow \quad f^{-1}(k) \leq x < f^{-1}(k+1) \quad \Leftrightarrow \quad k \leq f(x) < k+1 \\ &\Leftrightarrow \quad \lfloor f(x) \rfloor = k. \end{aligned}

Similar derivations can be shown for \lceil \cdot \rceil and we have

f(x)=f(x)andf(x)=f(x),\lfloor f(x) \rfloor = \lfloor f(\lfloor x \rfloor) \rfloor \quad \text{and} \quad \lceil f(x) \rceil = \lceil f(\lceil x \rceil) \rceil,

for this class of functions. For f(x)=xf(x) = \sqrt{x} we thus have

x=xandx=x.\left\lfloor \sqrt{x} \right\rfloor = \left\lfloor \sqrt{\lfloor x \rfloor} \right\rfloor \quad \text{and} \quad \left\lceil \sqrt{x} \right\rceil = \left\lceil \sqrt{\lceil x \rceil} \right\rceil.

Fractions

The result of the previous section also applies to f(x)=(x+n)/mf(x) = (x + n)/m for integer m,nm, n and m>0m > 0. The positivity of mm ensures that ff is monotonically increasing and f1(y)=mynf^{-1}(y) = m y - n is clearly integer for integer yy. We now have

x+nm=x+nmandx+nm=x+nm.\left\lfloor \frac{x+n}{m} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor+n}{m} \right\rfloor \quad \text{and} \quad \left\lceil \frac{x+n}{m} \right\rceil = \left\lceil \frac{\lceil x \rceil+n}{m} \right\rceil.

From these equalities we have the special cases

x/a1/a2/ak=xa1a2ak andx/a1/a2/ak=xa1a2ak,\begin{aligned} \left\lfloor \ldots \left\lfloor \lfloor x/a_1 \rfloor /a_2 \right\rfloor \ldots /a_k \right\rfloor &= \left\lfloor \frac{x}{a_1 a_2 \cdots a_k} \right\rfloor \text{ and} \\ \left\lceil \ldots \left\lceil \lceil x/a_1 \rceil /a_2 \right\rceil \ldots /a_k \right\rceil &= \left\lceil \frac{x}{a_1 a_2 \cdots a_k} \right\rceil, \end{aligned}

for integer and positive aja_j.

Let us now consider q=n/mq = \lfloor n/m \rfloor for integer m,nm, n and m>0m > 0. We get

q=nm    nm1<qnm    nm<qmn    qmn<(q+1)m  qmn(q+1)m1,\begin{aligned} q=\left\lfloor \frac{n}{m} \right\rfloor \;&\Leftrightarrow\; \frac{n}{m}-1 < q \leq \frac{n}{m} \;\Leftrightarrow\; n-m < q m \leq n \;\Leftrightarrow\; q m \leq n < (q+1) m \\ &\Leftrightarrow\; q m \leq n \leq (q+1) m - 1, \end{aligned}

which provides an interval of integers for the numerator nn. Similarly for the ceil function,

q=nm    nmq<nm+1    nqm<n+m    (q1)m<nqm  (q1)m+1nqm.\begin{aligned} q=\left\lceil \frac{n}{m} \right\rceil \;&\Leftrightarrow\; \frac{n}{m} \leq q < \frac{n}{m}+1 \;\Leftrightarrow\; n \leq q m < n+m \;\Leftrightarrow\; (q-1) m < n \leq q m \\ &\Leftrightarrow\; (q-1) m+1 \leq n \leq q m. \end{aligned}

When applying floor or ceil to rational numbers, one can be derived from the other. Since (q1)m+1nqm(q-1) m+1 \leq n \leq q m can be rewritten as qmn+m1(q+1)m1q m \leq n+m-1 \leq (q+1) m - 1 we get

nm=n+m1m,\left\lceil \frac{n}{m} \right\rceil = \left\lfloor \frac{n+m-1}{m} \right\rfloor,

and similarly

nm=nm+1m.\left\lfloor \frac{n}{m} \right\rfloor = \left\lceil \frac{n-m+1}{m} \right\rceil.

Logarithms

Let logbx\log_b x be the logarithm of xx, base bb (x1x \geq 1, b>0b > 0, b1b \neq 1). We first set f(x)=logbxf(x) = \log_b x for integer bb, base 22 or 1010 being the most common. Again, we can apply the theorem from earlier; ff is continuous and monotonically increasing and f1(y)=byf^{-1}(y) = b^y is integer for integer y0y \geq 0, so we have

logbx=logbxandlogbx=logbx,\left\lfloor \log_b x \right\rfloor = \left\lfloor \log_b \lfloor x \rfloor \right\rfloor \quad \text{and} \quad \left\lceil \log_b x \right\rceil = \left\lceil \log_b \lceil x \rceil \right\rceil,

for integer b2b \geq 2 and x1x \geq 1.

We conclude with some straightforward, but quite useful, statements:

k=logbx    klogbx<k+1    bkx<bk+1k = \lfloor \log_b x \rfloor \;\Leftrightarrow\; k \leq \log_b x < k+1 \;\Leftrightarrow\; b^k \leq x < b^{k+1}

and

k=logbx    k1<logbxk    bk1<xbk,k = \lceil \log_b x \rceil \;\Leftrightarrow\; k-1 < \log_b x \leq k \;\Leftrightarrow\; b^{k-1} < x \leq b^k,

for integer kk and all b>0b > 0, b1b \neq 1.

References

Most of the material presented in this article can be found in some form in Concrete Mathematics by R. L. Graham, D. E. Knuth, and O. Patashnik, and in The Art of Computer Programming, Volume 1, by Donald E. Knuth.

The Wikipedia page Floor and ceiling functions furthermore lists a lot of properties (very few proofs or derivations, though).

Commenting is not possible for this post, but feel free to leave a question, correction or any comment by using the contact page