TAOCP 1.2.2 Exercise 6

Let x=m+0.

taocpmathematicsalgorithmsvolume-1simple

Section 1.2.2: Numbers, Powers, and Logarithms

Exercise 6. [10] Let $x = m + 0.d_1 d_2 \ldots$ and $y = n + 0.e_1 e_2 \ldots$ be real numbers. Give a rule for determining whether $x = y$, $x < y$, or $x > y$, based on the decimal representation.

Verified: yes
Solve time: 1m58s

Let

$$ x=m+0.d_1d_2d_3\cdots,\qquad y=n+0.e_1e_2e_3\cdots, $$

where the decimal representations are taken in the canonical form used for real numbers, namely the representation that is not eventually all $9$'s. With this convention, each real number has a unique decimal representation.

We determine the relation between $x$ and $y$ as follows.

First compare the integer parts.

  • If $m<n$, then $x<y$.
  • If $m>n$, then $x>y$.

Now suppose $m=n$.

If $d_i=e_i$ for every $i\ge1$, then the decimal representations are identical. Since canonical decimal representations are unique, it follows that $x=y$.

Otherwise, let $k$ be the first position at which the digits differ:

$$ d_1=e_1,\ \ldots,\ d_{k-1}=e_{k-1},\qquad d_k\ne e_k. $$

Then

$$ x = m+\sum_{i=1}^{k-1}\frac{d_i}{10^i} +\frac{d_k}{10^k} +\sum_{i=k+1}^{\infty}\frac{d_i}{10^i}, $$

$$ y = m+\sum_{i=1}^{k-1}\frac{e_i}{10^i} +\frac{e_k}{10^k} +\sum_{i=k+1}^{\infty}\frac{e_i}{10^i}. $$

Since the first $k-1$ digits agree,

$$ x-y = \frac{d_k-e_k}{10^k} + \sum_{i=k+1}^{\infty}\frac{d_i-e_i}{10^i}. $$

The absolute value of the tail satisfies

$$ \left| \sum_{i=k+1}^{\infty}\frac{d_i-e_i}{10^i} \right| \le \sum_{i=k+1}^{\infty}\frac{9}{10^i} = \frac1{10^k}. $$

Because $d_k-e_k$ is a nonzero integer, $|d_k-e_k|\ge1$. Hence the sign of $x-y$ is determined by the sign of $d_k-e_k$. Therefore

$$ d_k<e_k \implies x<y, \qquad d_k>e_k \implies x>y. $$

Thus the comparison rule is:

$$ \boxed{ \begin{array}{l} \text{Compare } m \text{ and } n.\[2mm] \text{If } m=n,\text{ compare the decimal digits from left to right.}\[2mm] \text{At the first position where the digits differ,}\ \text{the number with the smaller digit is the smaller real number.}\[2mm] \text{If all digits agree, the numbers are equal.} \end{array} } $$

The restriction to canonical decimal representations is essential; otherwise one would have equal numbers such as

$$ 1.000\ldots = 0.999\ldots, $$

whose decimal representations are different.