TAOCP 4.1 Exercise 7

Represent each real number by a decimal expansion extending infinitely in both directions, x=\cdots d_2d_1d_0.

taocpmathematicsalgorithmsvolume-2

Section 4.1: Positional Number Systems

Exercise 7. [**] [M20] The text defines ten's complement notation only for integers represented in a single computer word. Is there a way to define a ten's complement notation for all real numbers, having "infinite precision," analogous to the text's definition? Is there a similar way to define a nines' complement notation for all real numbers?

Verified: yes
Solve time: 2m28s

Represent each real number by a decimal expansion extending infinitely in both directions,

$$ x=\cdots d_2d_1d_0.d_{-1}d_{-2}\cdots , $$

where each $d_k\in{0,1,\ldots,9}$, and where all sufficiently far left digits are $0$ for nonnegative numbers. As usual, we exclude expansions ending in an infinite string of $9$s, so that the representation is unique.

We first consider nines' complement.

For a real number

$$ x=\cdots d_2d_1d_0.d_{-1}d_{-2}\cdots, $$

define its nines' complement $N(x)$ digitwise by

$$ N(x)=\cdots (9-d_2)(9-d_1)(9-d_0).(9-d_{-1})(9-d_{-2})\cdots. $$

This is well defined, since each digit is independently replaced by another digit in ${0,\ldots,9}$.

Let

$$ x_n=d_n10^n+\cdots+d_0+\sum_{k=1}^\infty d_{-k}10^{-k} $$

be the truncation of $x$ at the $10^n$-place, and similarly let $N(x)_n$ be the corresponding truncation of $N(x)$. Then

$$ x_n+N(x)n = \sum{k=-\infty}^{n}9\cdot10^k. $$

The finite geometric sum gives

$$ \sum_{k=-m}^{n}9\cdot10^k = 10^{n+1}-10^{-m}, $$

and letting $m\to\infty$ yields

$$ x_n+N(x)_n=10^{n+1}. $$

Equivalently,

$$ N(x)=\cdots999999-x. $$

Thus nines' complement extends naturally to all real numbers by digitwise complementation.

Now consider ten's complement.

In finite precision with $n+1$ digits, ten's complement is obtained from nines' complement by adding $1$:

$$ T_n(x)=N_n(x)+1. $$

For infinite decimal expansions this construction fails. Indeed, suppose we tried to define

$$ T(x)=N(x)+10^{-m} $$

for some position $m$, analogous to adding $1$ in the finite case. Since $N(x)$ has infinitely many digits to the right, adding $10^{-m}$ requires carry propagation through infinitely many positions whenever the tail of $N(x)$ consists of $9$s. There is no distinguished leftmost digit at which the carry terminates.

More fundamentally, finite ten's complement depends on a modulus $10^{n+1}$:

$$ T_n(x)=10^{n+1}-x. $$

As $n\to\infty$, the quantity $10^{n+1}$ does not converge to a real number. Hence there is no real number that plays the role of the infinite string

$$ 100000\cdots $$

with infinitely many digits to the left. Therefore there is no corresponding real-valued operation analogous to ten's complement for all real numbers.

So the situation is as follows:

  1. Nines' complement extends naturally to all real numbers by replacing every digit $d_k$ by $9-d_k$.
  2. Ten's complement does not admit a corresponding extension to all real numbers, because its definition essentially depends on a finite modulus $10^{n+1}$, and there is no infinite real analogue of that modulus.