TAOCP 1.2.4 Exercise 5

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 5. [16] Given that $x$ is a positive real number, state a simple formula that expresses $x$ rounded to the nearest integer. The desired rounding rule is to produce $\lfloor x \rfloor$ when $x \bmod 1 < \tfrac12$, and to produce $\lceil x \rceil$ when $x \bmod 1 \ge \tfrac12$. Your answer should be a single formula that covers both cases. Discuss the rounding that would be obtained by your formula when $x$ is negative.

Verified: no
Solve time: 39s

Solution

Let $x$ be a positive real number. By definition, $x \bmod 1$ is the fractional part of $x$, so that

$x = \lfloor x \rfloor + (x \bmod 1), \qquad 0 \le x \bmod 1 < 1 \text{ by equation (4)}.$

The rounding rule states that $x$ should be rounded down to $\lfloor x \rfloor$ if $x \bmod 1 < \tfrac12$, and rounded up to $\lceil x \rceil$ if $x \bmod 1 \ge \tfrac12$.

Observe that adding $\tfrac12$ to $x$ produces

$x + \tfrac12 = \lfloor x \rfloor + (x \bmod 1) + \tfrac12.$

If $x \bmod 1 < \tfrac12$, then $0 \le x \bmod 1 + \tfrac12 < 1$, so

$\lfloor x + \tfrac12 \rfloor = \lfloor x \rfloor.$

If $x \bmod 1 \ge \tfrac12$, then $1 \le x \bmod 1 + \tfrac12 < 1.5$, so

$\lfloor x + \tfrac12 \rfloor = \lfloor x \rfloor + 1 = \lceil x \rceil.$

Therefore, for positive $x$, the rounding to the nearest integer can be expressed by the single formula

$\boxed{\text{round}(x) = \lfloor x + \tfrac12 \rfloor}.$

For negative $x$, write $x = -y$ with $y > 0$. Then

$\text{round}(x) = -\text{round}(y) = -\lfloor y + \tfrac12 \rfloor.$

Equivalently, using the ceiling function,

$\text{round}(x) = \lceil x - \tfrac12 \rceil, \qquad x < 0.$

This completes the proof.

∎