TAOCP 4.3.3: How Fast Can We Multiply?
Section 4.3.3 exercises: 17/19 solved.
Section 4.3.3. How Fast Can We Multiply?
Exercises from TAOCP Volume 2 Section 4.3.3: 17/19 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [**] | solved | 8m42s | |
| 2 | [M22] | math-medium | - | - |
| 3 | [M22] | math-medium | verified | 4m34s |
| 4 | ▶ [**] | verified | 7m14s | |
| 5 | ▶ [**] | - | - | |
| 6 | [M23] | math-medium | solved | 4m45s |
| 7 | [M23] | math-medium | verified | 2m50s |
| 8 | [M20] | math-medium | verified | 1m24s |
| 9 | [M15] | math-simple | verified | 4m51s |
| 10 | [M26] | math-hard | verified | 3m59s |
| 11 | ▶ [M26] | math-hard | verified | 3m11s |
| 12 | ▶ [M41] | math-project | verified | 1m59s |
| 13 | [M25] | math-medium | verified | 1m16s |
| 14 | [M2] | math-simple | solved | 8m16s |
| 15 | [M49] | math-research | verified | 5m57s |
| 16 | ▶ [**] | verified | 8m46s | |
| 17 | [M26] | math-hard | solved | 8m58s |
| 18 | ▶ [M30] | math-hard | solved | 5m51s |
| 19 | ▶ [M23] | math-medium | verified | 6m56s |
TAOCP 4.3.3 Exercise 1
We are asked to compute 1234 \cdot 2341 using the decimal analogue of the method in (2) (Karatsuba-type divide-and-conquer multiplication).
TAOCP 4.3.3 Exercise 3
For $k>0$, the desired inequality is 2^{q_k+1}(2r_k)^{r_k}\le 2^{q_{k-1}+q_k}.
TAOCP 4.3.3 Exercise 4
**Exercise 4.
TAOCP 4.3.3 Exercise 6
We are asked to prove that the six numbers in equation (24) of Section 4.
TAOCP 4.3.3 Exercise 7
We are asked to show that if in step T1 of Algorithm T we replace the original initialization $R \leftarrow \lfloor \sqrt{Q} \rfloor$ by $R \leftarrow \lceil \sqrt{2Q} \rceil + 1,$ then the bound on t...
TAOCP 4.3.3 Exercise 8
The assertion that $u_{j+n} = 0$ at the beginning of step D3 of Algorithm D is false.
TAOCP 4.3.3 Exercise 9
Let $k$ be the length of the discrete Fourier transform and let $\omega = e^{2\pi i / k}$ be a primitive $k$th root of unity.
TAOCP 4.3.3 Exercise 10
Let $n$ be the bit length of the inputs to the Schönhage–Strassen multiplication algorithm, and let $\tilde{u}_s$, $\tilde{v}_s$, $\tilde{w}_s$ denote the discrete Fourier transforms (DFTs) used in th...
TAOCP 4.3.3 Exercise 11
Let the linear iterative array be the family of automata M_0,M_1,M_2,\ldots defined by equations (37) and (38).
TAOCP 4.3.3 Exercise 12
The machine of the exercise has only node creation, pointer manipulation, equality tests, input, and output.
TAOCP 4.3.3 Exercise 13
Let $T(n)$ denote the time needed to multiply two $n$-bit numbers by one of the fast multiplication methods discussed in this section.
TAOCP 4.3.3 Exercise 14
Algorithm T is Knuth's Toom-Cook multiplication algorithm.
TAOCP 4.3.3 Exercise 15
We are asked to determine the fastest possible online multiplication algorithms on various species of automata.
TAOCP 4.3.3 Exercise 16
**Exercise 4.
TAOCP 4.3.3 Exercise 17
We are asked to solve the Karatsuba recurrence K_1 = 1, \quad K_{2n} = 3 K_n, \quad K_{2n+1} = 2 K_{n+1} + K_n \quad (n \ge 1), and to find an explicit formula for $K_n$ when