Exercises from Section 1.2.2

5. [05] We deﬁned real numbers in terms of a decimal expansion. Discuss how we could have deﬁned them in terms of a binary expansion instead, and give a deﬁnition to replace Eq. (2).

We could have deﬁned real numbers in terms of a binary expansion by simply using the base two number system instead of base ten.

A real number is a quantity $x$ that has a binary expansion

x = n + 0 . d_{1} d_{2} d_{3} \dots,

(5.1)

where $n$ is an integer, each $d_{i}$ is a digit between $0$ and $1$ , and the sequence of digits doesn’t end with inﬁnitely many $1$ s. The representation (5.1) means that

n + \frac{d_{1}}{2} + \frac{d_{2}}{4} + \dots + \frac{d_{k}}{2^{k}} \leq x < n + \frac{d_{1}}{2} + \frac{d_{2}}{4} + \dots + \frac{d_{k}}{2^{k}} + \frac{1}{2^{k}},

(5.2)

for all positive integers $k$ .

6. [10] Let

x = m + 0 . d_{1} d_{2} \dots

and

y = n + 0 . e_{1} e_{2} \dots

be real numbers. Give a rule for determining whether

x = y

x < y

, or

x > y

, based on the decimal representation.

Given $x = m + 0 . d_{1} d_{2} \dots$ and $y = n + 0 . e_{1} e_{2} \dots$ be real numbers, we can deﬁne the following relations.

$x = y$ . $x$ is equivalent to $y$ if $m = n$ and $d_{i} = e_{i}$ for all $i \geq 1$ .

$x < y$ . $x$ is less than $y$ if either $m < n$ or ( $m = n$ and) $d_{1} < e_{1}$ or ( $m = n$ and) $d_{i} = e_{i}$ for all $1 \leq i < k$ and $d_{k} < e_{k}$ .

$x > y$ . $x$ is greater than $y$ if either $m > n$ or ( $m = n$ and) $d_{1} > e_{1}$ or ( $m = n$ and) $d_{i} = e_{i}$ for all $1 \leq i < k$ and $d_{k} > e_{k}$ .

7. [M23] Given that

x

and

y

are integers, prove the laws of exponents, starting from the deﬁnition given by Eq. (4).

Given integers $x$ , $y$ ; a positive real number $b$ ; and Eq. (4) on page 22, we may prove Eq. (5).

Proposition. $b^{x + y} = b^{x} b^{y}$ for any positive real number $b$ and integers $x$ , $y$ .

Proof. Assume $b$ an arbitrary positive real and $x$ , $y$ integers. We must show that $b^{x + y} = b^{x} b^{y}$ . If $x = 0$ , then clearly:

\begin{array}{l} b^{x + y} & = b^{0 + y} \\ = b^{y} \\ = (1) b^{y} \\ = b^{0} b^{y} \\ = b^{x} b^{y} \end{array}

Then, for the inductive step, we consider two cases, $x \geq 0$ and $x \leq 0$ .

Case 1. [ $x \geq 0$ .] Assuming $b^{k + y} = b^{k} b^{y}$ for $k \geq 0$ , we must show that $b^{(k + 1) + y} = b^{k + 1} b^{y}$ . But:

\begin{array}{l} b^{(k + 1) + y} & = b^{k + y + 1} \\ = b^{k + y} b^{1} \\ = b^{k} b^{y} b^{1} \\ = b^{k} b^{1} b^{y} \\ = b^{k + 1} b^{y} \end{array}

as we needed to show in this case.

Case 2. [ $x \leq 0$ .] Assuming $b^{k + y} = b^{k} b^{y}$ for $k \leq 0$ , we must show that $b^{(k - 1) + y} = b^{k - 1} b^{y}$ . But:

\begin{array}{l} b^{(k - 1) + y} & = b^{k + y - 1} \\ = b^{k + y} b^{- 1} \\ = b^{k} b^{y} b^{- 1} \\ = b^{k} b^{- 1} 1 b^{y} \\ = b^{k - 1} b^{y} \end{array}

as we needed to show in this case.

Therefore, $b^{x + y} = b^{x} b^{y}$ for any positive real number $b$ and integers $x$ , $y$ as we needed to show. □

Proposition. ${(b^{x})}^{y} = b^{x y}$ for any positive real number $b$ and integers $x$ , $y$ .

Proof. Assume $b$ an arbitrary positive real and $x$ , $y$ integers. We must show that ${(b^{x})}^{y} = b^{x y}$ . If $x = 0$ , then clearly:

\begin{array}{l} {(b^{0})}^{y} & = 1^{y} \\ = 1 \\ = b^{0} \\ = b^{0 y} \\ = b^{x y} \end{array}

Then, for the inductive step, we consider two cases, $x \geq 0$ and $x \leq 0$ .

Case 1. [ $x \geq 0$ .] Assuming ${(b^{k})}^{y} = b^{k y}$ for $k \geq 0$ , we must show that ${(b^{k + 1})}^{y} = b^{(k + 1) y}$ . But from the previous proposition:

\begin{array}{l} {(b^{k + 1})}^{y} & = {(b^{k} b^{1})}^{y} \\ = {(b^{k} b)}^{y} \\ = {(b^{k})}^{y} b^{y} \\ = b^{k y} b^{y} \\ = b^{k y + y} \\ = b^{(k + 1) y} \end{array}

as we needed to show in this case.

Case 2. [ $x \leq 0$ .] Assuming ${(b^{k})}^{y} = b^{k y}$ for $k \leq 0$ , we must show that ${(b^{k - 1})}^{y} = b^{(k - 1) y}$ . But from the previous proposition:

\begin{array}{l} {(b^{k - 1})}^{y} & = {(b^{k} b^{- 1})}^{y} \\ = {(b^{k})}^{y} {(b^{- 1})}^{y} \\ = b^{k y} b^{- y} \\ = b^{k y - y} \\ = b^{(k - 1) y} \end{array}

as we needed to show in this case.

Therefore, ${(b^{x})}^{y} = b^{x y}$ for any positive real number $b$ and integers $x$ , $y$ as we needed to show. □

8. [25] Let

m

be a positive integer. Prove that every positive real number

u

has a unique positive

m

th root, by giving a method to construct successively the values

n, d_{1}, d_{2}, \dots

in the decimal expansion of the root.

Given a positive real number $u$ and positive integer $m$ , we may present a method to construct $\sqrt[m]{u} = n + d_{1} d_{2} \dots$ , and in so doing, prove that $\sqrt[m]{u}$ exists uniquely.

First, determine $n$ by evaluating for which integer $j \geq 0$

j^{m} \leq u < {(j + 1)}^{m}

and let $n = j$ .

Then, for $k \geq 1$ , we successively determine for which integers $d_{k}$ , $1 \leq d_{k} \leq 9$

{(n + \sum_{1 \leq i \leq k} \frac{d_{i}}{1 0^{i}})}^{m} \leq u < {(n + \sum_{1 \leq i \leq k} \frac{d_{i}}{1 0^{i}} + \frac{1}{1 0^{k}})}^{m}

for $k$ as great as we please.

9. [M23] Given that

x

and

y

are rational, prove the laws of exponents under the assumption that the laws hold when

x

and

y

are integers.

We may prove the laws of exponents for rational exponents, assuming the laws for integer exponents.

Proposition. $b^{x + y} = b^{x} b^{y}$ for any positive real number $b$ and rationals $x$ , $y$ .

Proof. Assume $b$ an arbitrary positive real and $x = p ∕ q$ , $y = r ∕ s$ rationals. We must show that $b^{x + y} = b^{x} b^{y}$ . But:

\begin{array}{l} b^{x + y} & = b^{p ∕ q + r ∕ s} \\ = b^{(p s + r q) ∕ (q s)} \\ = {(b^{p s + r q})}^{1 ∕ (q s)} \\ = {(b^{p s} b^{r q})}^{1 ∕ (q s)} \\ = {(b^{p s})}^{1 ∕ (q s)}) {(b^{r q})}^{1 ∕ (q s)} \\ = b^{p s ∕ q s} b^{r q ∕ q s} \\ = b^{p ∕ q} b^{r ∕ s} \\ = b^{x} b^{y} \end{array}

□

Proposition. ${(b^{x})}^{y} = b^{x y}$ for any positive real number $b$ and rationals $x$ , $y$ .

Proof. Assume $b$ an arbitrary positive real and $x = p ∕ q$ , $y = r ∕ s$ rationals. We must show that ${(b^{x})}^{y} = b^{x y}$ . But:

\begin{array}{l} {(b^{x})}^{y} & = {(b^{p ∕ q})}^{r ∕ s} \\ = {({(b^{p})}^{1 ∕ q})}^{r ∕ s} \\ = {(b^{p})}^{r ∕ (q s)} \\ = {(b^{p r})}^{1 ∕ (q s)} \\ = b^{(p r) ∕ (q s)} \\ = b^{(p ∕ q) (r ∕ s)} \\ = b^{x y} \end{array}

□

We may prove that $\log_{10} 2$ is not a rational number.

Proposition. $\log_{10} 2$ is irrational.

Proof. Assume that it is not. That is, assume $\log_{10} 2 = p ∕ q$ for some positive integers $p$ , $q$ . That is, assume $1 0^{p ∕ q} = 2$ or equivalently, $1 0^{p} = 2^{q}$ . But no such positive integers exist. Hence, $\log_{10} 2$ is irrational. □

▸

11. [10] If

b = 10

and

x \approx \log_{10} 2

, to how many decimal places of accuracy will we need to know the value of

x

in order to determine the ﬁrst three decimal places of the decimal expansion of

b^{x}

? [Note: You may use the result of exercise 10 in your discussion.]

As a result of the proof from exercise 10, since $\log_{10} 2$ is irrational, $b^{x}$ for $b = 10$ and $x = \log_{10} 2$ (that is, an irrational power $x$ of $10$ ), we may never know enough decimal places of $x$ in order to determine the ﬁrst three decimal places of the decimal expansion of $b^{x}$ .

Eq. (10) claims that

\log_{10} 2 = 0.30102999 \dots

and by the deﬁnition of Eq. (7) and results of Eqs. (8) we have that

1.9999999739 \dots = 1 0^{0.30102999} \leq 2 < 1 0^{0.30103000} = 2.0000000199 \dots

Taking logarithms yields

0.30102999 \leq \log_{10} 2 < 0.30103000

and so by deﬁnition of decimal expansion, $\log_{10} 2 = 0.30102999 \dots$ .

▸

13. [M23] (a) Given that

x

is a positive real number and

n

is a positive integer, prove the inequality

\sqrt[n]{1 + x} - 1 \leq x ∕ n

. (b) Use this fact to justify the remarks following (7).

First, we must prove a relation.

Proposition. $\sqrt[n]{1 + x} - 1 \leq x ∕ n$ for any positive real numbers $x$ and all positive integers $n$ .

Proof. Let $x$ by an arbitrary positive real number so that $x > 0$ . We must show that $\sqrt[n]{1 + x} - 1 \leq x ∕ n$ for all integers $n > 0$ , or equivalently, that $n y + 1 \leq {(y + 1)}^{n}$ for $y = x ∕ n$ .

For $n = 1$ , clearly $y + 1 \leq {(y + 1)}^{1}$ . Then, assuming $k y + 1 \leq {(y + 1)}^{k}$ for $k > 0$ , we must show that $(k + 1) y + 1 \leq {(y + 1)}^{k + 1}$ . But:

\begin{array}{l} (k + 1) y + 1 & = k y + 1 + y \\ \leq {(y + 1)}^{k} + y \\ \leq {(y + 1)}^{k} + (y + 1) \\ \leq {(y + 1)}^{k} (y + 1) \\ = {(y + 1)}^{k + 1} \end{array}

□

For $x = b - 1$ and $n = 1 0^{k}$ , this fact tells us that

\sqrt[1 0^{k}]{1 + (b - 1)} - 1 = b^{1 ∕ 1 0^{k}} - 1 \leq (b - 1) ∕ 1 0^{k}

Since $b^{n + d_{1} ∕ 10 + \dots + d_{k} ∕ 1 0^{k}} \leq b^{n + 1}$ , we have

b^{n + d_{1} ∕ 10 + \dots + d_{k} ∕ 1 0^{k}} b^{1 ∕ 1 0^{k}} - 1 \leq b^{n + 1} (b - 1) ∕ 1 0^{k}

for the diﬀerence $b^{n + d_{1} ∕ 10 + \dots + d_{k} ∕ 1 0^{k}} b^{1 ∕ 1 0^{k}} - 1 = b^{n + d_{1} ∕ 10 + \dots + d_{k} ∕ 1 0^{k} + 1 ∕ 1 0^{k}} - b^{n + d_{1} ∕ 10 + \dots + d_{k} ∕ 1 0^{k}}$ , which justiﬁes the remarks following Eq. (7).

We may prove Eq. (12).

Proposition. $\log_{b} (c^{y}) = y \log_{b} c$ if $c > 0$ .

Proof. Let $c > 0$ . We must show that $\log_{b} (c^{y}) = y \log_{b} c$ . By the laws of exponents:

c^{y} = {(b^{\log_{b} c})}^{y} = b^{y \log_{b} c}

Taking logarithms yields:

\log_{b} (c^{y}) = \log_{b} (b^{y \log_{b} c}) = y \log_{b} c

As we need to show. □

We are able to prove the proposition.

Proposition. $\log_{b} x ∕ y = \log_{b} x - \log_{b} y$ if $x, y > 0$ .

Proof. Let $x, y > 0$ . We must show that $\log_{b} x ∕ y = \log_{b} x - \log_{b} y$ . But by Eqs. (11) and (12):

\begin{array}{l} \log_{b} x - \log_{b} y & = \log_{b} x + \log_{b} (y^{- 1}) \\ = \log_{b} x + \log_{b} (1 ∕ y) \\ = \log_{b} x ∕ y \end{array}

As we needed to show. □

By Eq. (14)

\log_{10} x = \frac{\ln x}{\ln 10} .

▸

17. [05] What is

\lg 32

\log_{π} π

\ln e

\log_{b} 1

\log_{b} (- 1)

Since $2^{5} = 32$ ,

\lg 32 = 5 .

Since $π^{1} = π$ ,

\log_{π} π = 1 .

Since $e^{1} = e$ ,

\ln e = 1 .

By the law of exponents, that $b^{0} = 1$ , we have

\log_{b} 1 = 0;

but since $b^{n} \geq 0$ for all positive real numbers $b$ and integers $n$ ,

\log_{b} (- 1)

is undeﬁned.

We are able to disprove the proposition, by way of counterexample. Consider $x = 8$ . $\log_{8} x = \log_{8} 8 = 1 \neq \frac{3}{2} = \frac{1}{2} \lg 8 = \frac{1}{2} \lg x$ .

▸

19. [20] If

n

is an integer whose decimal representation is 14 digits long, will the value of

n

ﬁt in a computer word with a capacity of 47 bits and a sign bit?

If $n$ is an integer whose decimal representation is 14 digits long, then we have that $n < 1 0^{14}$ , or equivalently that $\log_{10} n < 14$ . We can convert this to the binary case by converting logarithms.

\begin{array}{l} \log_{10} n < 14 & \Rightarrow n < 1 0^{14} \\ \Rightarrow \ln n < \ln 1 0^{14} \end{array}

Note that $\ln 1 0^{14} = 14 \ln 10 < 14 \times 3 = 42 < 47$ , so that $\ln n < 47$ . That is, the binary representation of an integer $n$ whose decimal representation is 14 digits long will ﬁt within 47 bits (and a sign bit).

$\log_{10} 2$ and $\log_{2} 10$ are reciprocals of each other. That is, $\log_{10} 2 = \frac{\ln 2}{\ln 10}$ and $\log_{2} 10 = \frac{\ln 10}{\ln 2}$ .

21. [15] (Logs of logs.) Express

\log_{b} \log_{b} x

in terms of

\ln \ln x

\ln \ln b

, and

\ln b

We can express $\log_{b} \log_{b} x$ in terms of $\ln \ln x$ , $\ln \ln b$ , and $\ln b$ as follows:

\begin{array}{l} \log_{b} \log_{b} x & = \log_{b} \frac{\ln x}{\ln b} \\ = \log_{b} \ln x - \log_{b} \ln b \\ = \frac{\ln \ln x}{\ln b} - \frac{\ln \ln b}{\ln b} \\ = \frac{\ln \ln x - \ln \ln b}{\ln b} . \end{array}

with less than 1% error! (Thus a table of natural logarithms and of common logarithms can be used to get approximate values of binary logarithms as well.)

We are able to prove that $\lg x \approx \ln x + \log_{10} x$ with less than 1% error.

Proposition. $\lg x \approx \ln x + \log_{10} x$ with less than 1% error.

Proof. Let $x$ be an arbitrary positive real number. We must show that $\lg x \approx \ln x + \log_{10} x$ with less than 1% error; that is, we must show that $| \frac{\ln x + \log_{10} x - \lg x}{\lg x} | < 0.01$ . But:

\begin{array}{l} | \frac{\ln x + \log_{10} x - \lg x}{\lg x} | & = | \frac{\ln x + \frac{\ln x}{\ln 10} - \frac{\ln x}{\ln 2}}{\frac{\ln x}{\ln 2}} | \\ = | \frac{\ln 2 \ln x + \frac{\ln 2}{\ln 10} \ln x - \ln x}{\ln x} | \\ = | \ln 2 + \frac{\ln 2}{\ln 10} - 1 | \\ < 0.01 \end{array}

as we needed to show. □

23. [M25] Give a geometric proof that

\ln x y = \ln x + \ln y

based on Fig. 6.

We know from the integral calculus that $\ln x + \ln y = \ln x y$ since by deﬁnition $\ln x = \int_{1}^{x} \frac{1}{u} d u$ and

\begin{array}{l} \ln x + \ln y & = \int_{1}^{x} \frac{1}{u} d u + \int_{1}^{y} \frac{1}{v} d v \\ = \int_{1}^{x} \frac{1}{u} d u + \int_{1}^{y} \frac{1}{x w} d (x w) \\ = \int_{1}^{x} \frac{1}{u} d u + \int_{x}^{x y} \frac{1}{u} d u \\ = \int_{1}^{x y} \frac{1}{u} d u \end{array}

We can see this geometrically by observing ﬁrst the areas for $\ln x$

and $\ln y$ separately.

We then transform the area for $\ln y$ in such a way as to preserve its area, by dividing its height by $x$ while multiplying its width by $x$ , which yields an equivalent area, but shifted to the right.

These two areas can in fact be arranged continguously, giving us exactly the area for $\ln x y$ .

24. [15] Explain how the method used for calculating logarithms to the base 10 at the end of this section can be modiﬁed to produce logarithms to base 2.

We will show how to calculate $\log_{2} x$ and to express the answer in the binary system, as

\log_{2} x = n + b_{1} ∕ 2 + b_{2} ∕ 4 + b_{3} ∕ 8 + \dots .

First we shift the decimal point of $x$ to the left or to the right so that we have $1 \leq x ∕ 2^{n} < 2$ ; this determines the integer part, $n$ . To obtain $b_{1}, b_{2}, \dots$ , we now set $x_{0} = x ∕ 2^{n}$ and, for $k \geq 1$ ,

\begin{array}{l} b_{k} = 0, & x_{k} = x_{k - 1}^{2}, & if x_{k - 1}^{2} < 2; \\ b_{k} = 1, & x_{k} = x_{k - 1}^{2} ∕ 2, & if x_{k - 1}^{2} \geq 2 . \end{array}

The validity of this procedure follows from the fact that

1 \leq x_{k} = x^{2^{k}} ∕ 2^{2^{k} (n + b_{1} ∕ 2 + \dots + b_{k} ∕ 2^{k})} < 2,

for $k = 0, 1, 2, \dots$ .

25. [22] Suppose that we have a binary computer and a number

x

1 \leq x < 2

. Show that the following algorithm, which uses only shifting, addition, and subtraction operations proportional to the number of places of accuracy desired, may be used to calculate an approximation to

y = \log_{b} x

[Notes: This method is very similar to the method used for division in computer hardware. The idea goes back in essence to Henry Briggs, who used it (in decimal rather than binary form) to compute logarithm tables, published in 1624. We need an auxiliary table of the constants

\log_{b} 2

\log_{b} (4 ∕ 3)

\log_{b} (8 ∕ 7)

, etc., to as many values as the precision of the computer. The algorithm involves intentional computational errors, as numbers are shifted to the right, so that eventually

x

will be reduced to

1

and the algorithm will terminate. The purpose of this exercise is to explain why it will terminate and why it computes an approximation to

\log_{b} x

The algorithm relies on the identity

\log_{b} (x) = \log_{b} (x \frac{2^{k} - 1}{2^{k}} \frac{2^{k}}{2^{k} - 1}) = \log_{b} (x - \frac{x}{2^{k}}) + \log_{b} (\frac{2^{k}}{2^{k} - 1})

and the fact that

z \approx \frac{x}{2^{k}}

so that $y + \log_{b} (x) \approx \log_{b} (x_{0})$ for initial $x$ , $x_{0}$ .

To see this is the case, note that after L1, since $y = 0$ and $x = x_{0}$ , we have $y + \log_{b} (x) \approx \log_{b} (x_{0})$ . At L2, if $x = 1$ , $\log_{b} (x) = \log_{b} (1) = 0$ , and so we stop with $y + \log_{b} (x) = y \approx \log_{b} (x_{0})$ . Otherwise, we continue with $x > 1$ . Through L3, we maintain the invariant $z \approx \frac{x}{2^{k}}$ , until ﬁnally $x - z \geq 1$ , $x > 1$ , $z \geq 0$ , and $x > z$ . After L4, $y + \log_{b} (x) \approx \log_{b} (x_{0})$ is transformed by assignments into $y + \log_{b} (\frac{2^{k}}{2^{k} - 1}) + \log_{b} (x - \frac{x}{2^{k}}) \approx \log_{b} (x_{0})$ , which is equivalent to $y + \log_{b} (x) \approx \log_{b} (x_{0})$ , the same assertion as previously held before L2, with $x$ approaching $1$ as $z$ approaches $0$ , ultimately terminating when $x = 1$ .

26. [M27] Find a rigorous upper bound on the error made by the algorithm in the previous exercise, based on the precision used in the arithmetic operations.

We want to determine an upper bound on the error made by the algorithm in the previous exercise, based on the precision $p$ , the number of fractional digits. That is, the relative error $𝜖$ such that

| \frac{y + \log_{b} (x)}{\log_{b} (x_{0})} - 1 | \leq 𝜖

for initial $x$ , $x_{0}$ .

According to Brigg’s method, we have $\log_{b} (x) = \sum_{1 \leq k} (m_{k} \log_{b} (\frac{2^{k}}{2^{k} - 1}))$ with $0 \leq m_{k} < 2$ . In our approximation, however, we add at most $p$ terms, and each is truncated by the limited precision $p$ , giving us the following sum:

\sum_{1 \leq k \leq p} \frac{⌊ 2^{p} \log_{b} (\frac{2^{k}}{2^{k} - 1}) ⌋}{2^{p}}

with all $m_{k} = 1$ , the worst possible truncation. And according to the method, the above sum is an approximation of a factorization, giving us the following logarithm:

\log_{b} \prod_{1 \leq k \leq p} \frac{2^{k}}{2^{k} - 1}

And so, the upper bound on the error based on the precision $p$ is precisely:

| \frac{y + \log_{b} (x)}{\log_{b} (x_{0})} - 1 | \leq 𝜖 = | \frac{\sum_{1 \leq k \leq p} \frac{⌊ 2^{p} \log_{b} (\frac{2^{k}}{2^{k} - 1}) ⌋}{2^{p}}}{\log_{b} \prod_{1 \leq k \leq p} \frac{2^{k}}{2^{k} - 1}} - 1 |

For example, for $b = 2$ and $p = 8$ , $𝜖 < 1 %$ .

▸

27. [M25] Consider the method for calculating

\log_{10} x

discussed in the text. Let

x_{k}^{'}

denote the computed approximation to

x_{k}

, determined as follows:

x (1 - δ) \leq 1 0^{n} x_{0}^{'} \leq x (1 + 𝜖)

; and in the determination of

x_{k}^{'}

by Eqs. (18), the quantity

y_{k}

is used in place of

{(x_{k - 1}^{'})}^{2}

, where

{(x_{k - 1}^{'})}^{2} (1 - δ) \leq y_{k} \leq {(x_{k - 1}^{'})}^{2} (1 + 𝜖)

and

1 \leq y_{k} < 100

. Here

δ

and

𝜖

are small constants that reﬂect the upper and lower errors due to rounding or trunctation. If

\log^{'} x

denotes the result of the calculations, show that after

k

steps we have

We may prove the bounds of the approximation.

Proposition. $\log_{10} x + 2 \log_{10} (1 - δ) - 1 ∕ 2^{k} < \log^{'} x \leq \log_{10} x + 2 \log_{10} (1 + 𝜖)$ after $k$ steps.

Proof. We must show that

\log_{10} x + 2 \log_{10} (1 - δ) - 1 ∕ 2^{k} < \log^{'} x \leq \log_{10} x + 2 \log_{10} (1 + 𝜖)

holds after $k$ steps. It is suﬃcient to show that

x^{2^{k}} {(1 - δ)}^{2^{k + 1} - 1} \leq 1 0^{2^{k} (n + \sum_{1 \leq j \leq k} (b_{j} ∕ 2^{j}))} x_{k}^{'} \leq x^{2^{k}} {(1 + 𝜖)}^{2^{k + 1} - 1}

since, by taking logarithms and given that $\log^{'} x = n + \sum_{1 \leq j \leq k} (b_{j} ∕ 2^{j})$ :

\begin{array}{l} 2^{k} \log_{10} x + 2^{k} \log_{10} (1 - δ) (2 - 1 ∕ 2^{k}) \leq 2^{k} \log^{'} x \leq 2^{k} \log_{10} x + 2^{k} \log_{10} (1 + 𝜖) (2 - 1 ∕ 2^{k}) \\ \Rightarrow \log_{10} x + \log_{10} (1 - δ) (2 - 1 ∕ 2^{k}) \leq \log^{'} x \leq \log_{10} x + \log_{10} (1 + 𝜖) (2 - 1 ∕ 2^{k}) \\ \Rightarrow \log_{10} x + 2 \log_{10} (1 - δ) \leq \log^{'} x \leq \log_{10} x + 2 \log_{10} (1 + 𝜖) \end{array}

It also given that

x (1 - δ) \leq 1 0^{n} x_{0}^{'} \leq x (1 + 𝜖)

and that

x_{k + 1}^{'} = 1 0^{b_{k + 1}} x_{'} k 2 .

First, we must show that the relation holds for $k = 0$ . But this case is given, as:

x^{2^{0}} {(1 - δ)}^{2^{0 + 1} - 1} \leq 1 0^{2^{0} (n + \sum_{1 \leq j \leq 0} (b_{j} ∕ 2^{j}))} x_{0}^{'} \leq x^{2^{0}} {(1 + 𝜖)}^{2^{k + 1} - 1}

Then, assuming the relation holds for arbitrary $k \geq 0$ :

x^{2^{k}} {(1 - δ)}^{2^{k + 1} - 1} \leq 1 0^{2^{k} (n + \sum_{1 \leq j \leq k} (b_{j} ∕ 2^{j}))} x_{k}^{'} \leq x^{2^{k}} {(1 + 𝜖)}^{2^{k + 1} - 1}

we must show it holds for $k + 1$ :

x^{2^{k + 1}} {(1 - δ)}^{2^{k + 2} - 1} \leq 1 0^{2^{k + 1} (n + \sum_{1 \leq j \leq k + 1} (b_{j} ∕ 2^{j}))} x_{k + 1}^{'} \leq x^{2^{k + 1}} {(1 + 𝜖)}^{2^{k + 2} - 1}

We may take squares of the induction hypothesis:

{(x^{2^{k}} {(1 - δ)}^{2^{k + 1} - 1})}^{2} \leq {(1 0^{2^{k} (n + \sum_{1 \leq j \leq k} (b_{j} ∕ 2^{j}))} x_{k}^{'})}^{2} \leq {(x^{2^{k}} {(1 + 𝜖)}^{2^{k + 1} - 1})}^{2}

and evalate each part in turn.

For the lower bound, since $(1 - δ) < 1$ , we have:

\begin{array}{l} {(x^{2^{k}} {(1 - δ)}^{2^{k + 1} - 1})}^{2} & \geq {(x^{2^{k}} {(1 - δ)}^{2^{k + 1} - 1})}^{2} (1 - δ) \\ = x^{2^{k} 2} {(1 - δ)}^{2 (2^{k + 1} - 1) + 1} \\ = x^{2^{k + 1}} {(1 - δ)}^{2^{k + 2} - 1} \end{array}

For the upper bound, since $(1 + δ) > 1$ , we have:

\begin{array}{l} {(x^{2^{k}} {(1 + 𝜖)}^{2^{k + 1} - 1})}^{2} & \leq {(x^{2^{k}} {(1 + 𝜖)}^{2^{k + 1} - 1})}^{2} (1 + 𝜖) \\ = x^{2^{k} 2} {(1 + 𝜖)}^{2 (2^{k + 1} - 1) + 1} \\ = x^{2^{k + 1}} {(1 + 𝜖)}^{2^{k + 2} - 1} \end{array}

And for the middle approximation, since $x_{k + 1}^{'} = 1 0^{b_{k + 1}} x_{k}^{' 2}$ , we have:

\begin{array}{l} {(1 0^{2^{k} (n + \sum_{1 \leq j \leq k} (b_{j} ∕ 2^{j}))} x_{k}^{'})}^{2} & = 1 0^{2 (2^{k}) (n + \sum_{1 \leq j \leq k} (b_{j} ∕ 2^{j}))} 1 0^{b_{k + 1}} x_{k}^{' 2} ∕ 1 0^{b_{k + 1}} \\ = 1 0^{2^{k + 1} (n + \sum_{1 \leq j \leq k} (b_{j} ∕ 2^{j})) + 2^{k + 1} (b_{k + 1} ∕ 2^{k + 1})} x_{k + 1}^{'} \\ = 1 0^{2^{k + 1} (n + \sum_{1 \leq j \leq k} (b_{j} ∕ 2^{j}) + b_{k + 1} ∕ 2^{k + 1})} x_{k + 1}^{'} \\ = 1 0^{2^{k + 1} (n + \sum_{1 \leq j \leq k + 1} (b_{j} ∕ 2^{j}))} x_{k + 1}^{'} \end{array}

That is

x^{2^{k + 1}} {(1 - δ)}^{2^{k + 2} - 1} \leq 1 0^{2^{k + 1} (n + \sum_{1 \leq j \leq k + 1} (b_{j} ∕ 2^{j}))} x_{k + 1}^{'} \leq x^{2^{k + 1}} {(1 + 𝜖)}^{2^{k + 2} - 1}

as we needed to show. □

28. [HM30] (R. Feynman.) Develop a method for computing

b^{x}

when

0 \leq x < 1

, using only shifting, addition, and subtraction (similar to the algorithm in exercise 25), and analyze its accuracy.

The method below computes an approximation to $b^{x}$ for $0 \leq x < 1$ , using only shifting, addition, and subtraction, similar to the algorithm in exercise 25 in that it uses the same auxiliary table of constants.

Algorithm M (Digit-by-digit exponentiation.). Given a number $x$ , $0 \leq x < 1$ , calculate an approximation $y = b^{x}$ given machine precision $p$ .

M1.: [Initialize.] Set $x \leftarrow 1 - x$ , $y \leftarrow b$ , $k \leftarrow 1$ .
M2.: [Test for end.] If $x \leq 0$ , stop.
M3.: [Compare.] If $x - \log_{b} (2^{k} ∕ (2^{k} - 1)) < 0$ and $k < p$ , $k \leftarrow k + 1$ , and repeat this step.
M4.: [Reduce values.] Set $x \leftarrow x - \log_{b} (2^{k} ∕ (2^{k} - 1))$ , $y \leftarrow y - (y shifted right k)$ , and go to M2. (Note that the operation on $y$ is equivalent to $y \leftarrow y \times (2^{k} - 1) ∕ 2^{k}$ .) $■$

While decreasing $x$ by $\log_{b} (2^{k} ∕ (2^{k} - 1)) = - \log_{b} ((2^{k} - 1) ∕ 2^{k})$ , we increase $y$ by $y (2^{k} - 1) ∕ 2^{k}$ , so that $y b^{- x}$ remains approximately constant.

The upper bound on the error made by the algorithm, based on the precision $p$ , the number of fractional digits, can be represented by the relative error $𝜖$ such that

| \frac{y b^{x}}{b^{x_{0}}} - 1 | \leq 𝜖

for initial $x$ , $x_{0}$ .

According to the digit-by-digit method, we have $b^{x} = \prod_{1 \leq k} {(\frac{2^{k}}{2^{k} - 1})}^{m_{k}}$ with $0 \leq m_{k} < 2$ . In our approximation, however, we multiply at most $p$ factors, and each is truncated by the limited precision $p$ , giving us the following product:

\prod_{1 \leq k \leq p} \frac{⌊ 2^{p} \frac{2^{k}}{2^{k} - 1} ⌋}{2^{p}}

with all $m_{k} = 1$ , the worst possible truncation. And according to the method, the above product is an approximation of a factorization, giving us the following logarithm:

b^{\sum_{1 \leq k \leq p} \log_{b} \frac{2^{k}}{2^{k} - 1}}

And so, the upper bound on the error based on the precision $p$ is precisely:

| \frac{y b^{x}}{b^{x_{0}}} - 1 | \leq 𝜖 = | \frac{\prod_{1 \leq k \leq p} \frac{⌊ 2^{p} \frac{2^{k}}{2^{k} - 1} ⌋}{2^{p}}}{b^{\sum_{1 \leq k \leq p} \log_{b} \frac{2^{k}}{2^{k} - 1}}} - 1 |

For example, for $b = 2$ and $p = 8$ , $𝜖 < 1 %$ .

________________________________________________________________________________

Note: Similar algorithms can be given for trigonometric functions; see J. E. Meggitt, IBM J. Res. and Dev. 6 (1962), 210-226; 7 (1963), 237-245. See also T. C. Chen, IBM J. Res. and Dev. 16 (1972), 380-388; V. S. Linsky, Vychisl. Mat. 2 (1957), 90-119; D. E. Knuth, Metafont: The Program (Reading, Mass.: Addison-Wesley, 1986), §120-§147.

29. [HM20] Let

x

be a real number greater than

1

. (a) For what real number

b > 1

b \log_{b} x

a minimum? (b) For what integer

b > 1

is it a minimum? (c) For what integer

b > 1

(b + 1) \log_{b} x

a minimum?

a.

Let

x

and

b

be real numbers greater than

1

b = e

is a minimum for

b \log_{b} x

. The minimum of

b \log_{b} x

is the minimum of

\frac{b}{\ln b}

, and

\frac{d}{d b} \frac{b}{\ln b} = \frac{\ln b - 1}{{(\ln b)}^{2}} = 0

if and only if

\ln b = 1

and

b = e

b.

Let

x

be a real number and

b

be an integer, both greater than

1

b = ⌈ e ⌉ = 3

is a minimum for

b \log_{b} x

, since

| \frac{⌈ e ⌉}{\ln ⌈ e ⌉} - e | < | \frac{⌊ e ⌋}{\ln ⌊ e ⌋} - e | .

c.

Let

x

be a real number and

b

be an integer, both greater than

1

b = ⌈ α ⌉ = 4

for

α = e^{W (\frac{1}{e}) + 1}

, the Lambert

W

-function or product logarithm, is the minimum of

(b + 1) \log_{b} x

. The minimum of

(b + 1) \log_{b} x

is the minimum of

\frac{b + 1}{\ln b}

, and

\frac{d}{d b} \frac{b + 1}{\ln b} = b \ln b - b - 1 = 0

if and only if

b = e^{W (\frac{1}{e}) + 1} = α

, and

| \frac{⌈ α ⌉ + 1}{\ln ⌈ α ⌉} - α | < | \frac{⌊ α ⌋ + 1}{\ln ⌊ α ⌋} - α | .

30. [12] Simplify the expression

{(\ln n)}^{\ln n ∕ \ln \ln n}

, assuming that

n > 1

and

n \neq e