TAOCP 4.3.1: The Classical Algorithms
Section 4.3.1 exercises: 37/43 solved.
Section 4.3.1. The Classical Algorithms
Exercises from TAOCP Volume 2 Section 4.3.1: 37/43 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [**] | verified | 3m26s | |
| 2 | [15] | simple | verified | 1m25s |
| 3 | [21] | medium | solved | 7m25s |
| 4 | [M21] | math-medium | - | - |
| 5 | [21] | medium | solved | 5m13s |
| 6 | ▶ [22] | medium | solved | 4m52s |
| 7 | [M26] | math-hard | verified | 1m45s |
| 8 | [M26] | math-hard | - | - |
| 9 | ▶ [21] | medium | verified | 1m44s |
| 10 | [18] | medium | solved | 3m05s |
| 11 | [10] | simple | verified | 1m16s |
| 12 | [16] | medium | - | - |
| 13 | [21] | medium | verified | 4m22s |
| 14 | ▶ [M23] | math-medium | solved | 45s |
| 15 | [M20] | math-medium | verified | 1m19s |
| 16 | [39] | project | verified | 1m29s |
| 17 | [M20] | math-medium | - | - |
| 18 | [M30] | math-hard | verified | 1m22s |
| 19 | ▶ [M21] | math-medium | solved | 2m48s |
| 20 | [M22] | math-medium | solved | 2m25s |
| 21 | ▶ [M23] | math-medium | verified | 3m53s |
| 22 | ▶ [24] | medium | verified | 1m09s |
| 23 | [M23] | math-medium | solved | 3m15s |
| 24 | [M20] | math-medium | - | - |
| 25 | [26] | hard | verified | 3m12s |
| 26 | [21] | medium | solved | 3m44s |
| 27 | [M20] | math-medium | solved | 2m17s |
| 28 | [M30] | math-hard | - | - |
| 29 | [**] | solved | 2m04s | |
| 30 | ▶ [**] | solved | 2m23s | |
| 31 | [**] | verified | 5m23s | |
| 32 | [**] | solved | 40s | |
| 33 | [**] | solved | 55s | |
| 34 | [**] | solved | 6m45s | |
| 35 | [**] | verified | 4m27s | |
| 36 | [**] | verified | 1m09s | |
| 37 | [**] | solved | 4m01s | |
| 38 | [**] | verified | 6m27s | |
| 39 | [**] | verified | 4m58s | |
| 40 | [M24] | math-medium | verified | 9m03s |
| 41 | ▶ [M26] | math-hard | verified | 8m14s |
| 42 | [HM35] | hm-hard | verified | 1m49s |
| 43 | [**] | verified | 20m01s |
TAOCP 4.3.1 Exercise 1
The exercise is historical rather than theorem proving.
TAOCP 4.3.1 Exercise 2
Let the $m$ given nonnegative $n$-place integers be (u^{(1)}_{n-1}\ldots u^{(1)}_0)_b,\; (u^{(2)}_{n-1}\ldots u^{(2)}_0)_b,\; \ldots,\; (u^{(m)}_{n-1}\ldots u^{(m)}_0)_b,
TAOCP 4.3.1 Exercise 3
Exercise 2 generalizes Algorithm A to the addition of $m$ nonnegative $n$-place numbers (u^{(1)}_{n-1}\cdots u^{(1)}_0)_b,\; (u^{(2)}_{n-1}\cdots u^{(2)}_0)_b,\; \ldots,\; (u^{(m)}_{n-1}\cdots u^{(m)}...
TAOCP 4.3.1 Exercise 5
Something went wrong.
TAOCP 4.3.1 Exercise 6
We are asked to **add two $n$-digit numbers in base $b$ from left to right**, writing each output digit only **once it is guaranteed that it cannot be affected by any carry from lower-order digits**.
TAOCP 4.3.1 Exercise 7
Let $u = (u_{n-1} \ldots u_0)_b$ and $v = (v_{n-1} \ldots v_0)_b$ be two independent, uniformly distributed $n$-place nonnegative integers in base $b$.
TAOCP 4.3.1 Exercise 9
We are asked to generalize Algorithm A (addition of nonnegative $n$-place integers in a fixed radix $b$) to a _mixed-radix_ number system, where the digits have bases $b_0, b_1, \ldots, b_{n-1}$ from...
TAOCP 4.3.1 Exercise 10
We analyze the effect of interchanging instructions in Program S, which implements subtraction of nonnegative integers according to Algorithm S.
TAOCP 4.3.1 Exercise 11
Let $u = (u_{n-1} \ldots u_1 u_0)_b$ and $v = (v_{n-1} \ldots v_1 v_0)_b$ be nonnegative $n$-place integers.
TAOCP 4.3.1 Exercise 13
We are asked to multiply an $n$-place nonnegative integer U = (u_{n-1} u_{n-2} \dots u_1 u_0)_b by a single-digit integer $v$, $0 \le v < b$, producing an $(n+1)$-place result
TAOCP 4.3.1 Exercise 14
Let U=(u_{m-1}\ldots u_1u_0)_b,\qquad V=(v_{n-1}\ldots v_1v_0)_b, and let
TAOCP 4.3.1 Exercise 15
Let U=(.
TAOCP 4.3.1 Exercise 16
Let U=(.
TAOCP 4.3.1 Exercise 18
Show that if $\hat{q}' = \left\lfloor \frac{u_n b + u_{n-1}}{v_{n-1} + 1} \right\rfloor,$ then $\hat{q}' \le q$, where $q$ is the quotient digit in the classical division algorithm.
TAOCP 4.3.1 Exercise 19
Let the exact quotient digit be $q$ in the classical long-division algorithm of Section 4.
TAOCP 4.3.1 Exercise 20
We adopt the notation of Exercises 19 and 20.
TAOCP 4.3.1 Exercise 21
**Solution (Exercise 4.
TAOCP 4.3.1 Exercise 22
We are asked to find a four-digit number $u$ divided by a three-digit number $v$ in base $b = 10$ for which step D6 of Algorithm D is necessary.
TAOCP 4.3.1 Exercise 23
Let u=(u_nu_{n-1}\ldots u_0)_b,\qquad v=(v_{n-1}v_{n-2}\ldots v_0)_b, with
TAOCP 4.3.1 Exercise 25
Step D1 of Algorithm D normalizes the divisor and dividend before quotient selection begins.
TAOCP 4.3.1 Exercise 26
Step D8 in Algorithm D is the **add-back correction**.
TAOCP 4.3.1 Exercise 27
We are asked to prove that at the beginning of step D8 in Algorithm D, the unnormalized remainder $(.u_{n-1} \ldots u_1 u_0)_b$ is always an exact multiple of the divisor $d$.
TAOCP 4.3.1 Exercise 29
The statement is false.
TAOCP 4.3.1 Exercise 30
In Algorithms A and S, the computation of each output digit $w_j$ depends on the corresponding input digits $u_j$ and $v_j$ as well as on the carry or borrow from the previous step.
TAOCP 4.3.1 Exercise 31
Let u=(u_{m+n-1}\cdots u_1 u_0)_3, \qquad v=(v_{n-1}\cdots v_1 v_0)_3, where the digits are balanced ternary,
TAOCP 4.3.1 Exercise 32
Let $\beta=2i$.
TAOCP 4.3.1 Exercise 33
Something went wrong.
TAOCP 4.3.1 Exercise 34
The essential requirement is that integers of arbitrary length be stored in linked memory, and that result digits be created directly in newly allocated nodes obtained from a free-storage list.
TAOCP 4.3.1 Exercise 35
Let a decuple-precision floating-point number be represented by two consecutive machine words (X_1,X_0).
TAOCP 4.3.1 Exercise 36
Let \phi = 2^m\frac{1+x}{1-x}, where $m$ is an integer chosen so that $|x|<1$.
TAOCP 4.3.1 Exercise 37
If $d$ is a power of 2 on a binary computer, then multiplication or division by $d$ can be accomplished by simple bit shifts.
TAOCP 4.3.1 Exercise 38
**Solution (corrected)** Let $u$ and $v$ be integers with $0 \le u, v < 2^n$.
TAOCP 4.3.1 Exercise 39
Let S=\sum_{k\ge0}\frac1{16^k}\left(\frac4{8k+1}-\frac2{8k+4}-\frac1{8k+5}-\frac1{8k+6}\right).
TAOCP 4.3.1 Exercise 40
Let $u$ be a $2n$-digit number and $v$ an $n$-digit number in radix $b$, such that $u \bmod v = 0$.
TAOCP 4.3.1 Exercise 41
Let $b$ be the radix, $w = (w_{n-1} \ldots w_1 w_0)_b$ an $n$-place integer with $\gcd(w,b) = 1$, and $w'$ a one-place integer satisfying $u_0 w' \equiv 1 \pmod b.$ We are asked to: a) Given $u = \pm(...