TAOCP 4.6.3: Evaluation of Powers
Section 4.6.3 exercises: 34/35 solved.
Section 4.6.3. Evaluation of Powers
Exercises from TAOCP Volume 2 Section 4.6.3: 34/35 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [**] | verified | 3m35s | |
| 2 | [**] | solved | 6m32s | |
| 3 | [**] | verified | 4m11s | |
| 4 | [**] | verified | 1m38s | |
| 5 | ▶ [**] | verified | 1m23s | |
| 6 | [M26] | math-hard | verified | 7m20s |
| 7 | [M21] | math-medium | solved | 6m36s |
| 8 | [M21] | math-medium | verified | 3m43s |
| 9 | ▶ [25] | medium | verified | 2m55s |
| 10 | [10] | simple | verified | 1m35s |
| 11 | ▶ [M26] | math-hard | solved | 7m21s |
| 12 | [M10] | math-simple | verified | 1m27s |
| 13 | [M21] | math-medium | verified | 1m57s |
| 14 | [M29] | math-hard | verified | 1m52s |
| 15 | [M9] | math-simple | solved | 4m27s |
| 16 | [HM15] | hm-simple | verified | 1m25s |
| 17 | [M25] | math-medium | solved | 2m18s |
| 18 | [HM24] | hm-medium | - | - |
| 19 | [M25] | math-medium | verified | 7m04s |
| 20 | [M20] | math-medium | verified | 5m44s |
| 21 | ▶ [M26] | math-hard | verified | 6m23s |
| 22 | [M26] | math-hard | verified | 1m18s |
| 23 | [M20] | math-medium | solved | 4m57s |
| 24 | ▶ [M22] | math-medium | solved | 4m38s |
| 25 | [20] | medium | verified | 1m26s |
| 26 | ▶ [M25] | math-medium | verified | 1m31s |
| 27 | [M23] | math-medium | solved | 4m31s |
| 28 | [**] | verified | 1m18s | |
| 29 | [**] | verified | 2m25s | |
| 30 | [**] | verified | 1m10s | |
| 31 | [**] | verified | 2m47s | |
| 32 | [**] | solved | 6m12s | |
| 33 | [**] | verified | 2m33s | |
| 34 | [**] | solved | 5m12s | |
| 35 | [**] | verified | 2m25s |
TAOCP 4.6.3 Exercise 1
**Corrected Solution for Exercise 4.
TAOCP 4.6.3 Exercise 2
**Problem.
TAOCP 4.6.3 Exercise 3
Let $M(n)$ denote the number of multiplications.
TAOCP 4.6.3 Exercise 4
Consider the binary and octal ($m = 8$) methods for evaluating $x^n$.
TAOCP 4.6.3 Exercise 5
Maintain, for each integer $j$ already present in the tree, two links: LINK0[$j$], pointing to the predecessor of $j$ on the unique path from the root; and LINK1[$j$], pointing to the next node on the...
TAOCP 4.6.3 Exercise 6
We are asked to show that the **decreasing-order power tree** produces a method of computing $x^n$ that requires **exactly the same number of multiplications as the binary method**.
TAOCP 4.6.3 Exercise 7
Let $B(n)$, $F(n)$, and $P(n)$ denote the numbers of multiplications used by the binary method, factor method, and power-tree method, respectively.
TAOCP 4.6.3 Exercise 8
Let $b(n)$ denote the number of multiplications used by the left-to-right binary method to compute $x^n$.
TAOCP 4.6.3 Exercise 9
We are asked to design an exponentiation procedure analogous to Algorithm A, but based on radix $m = 2^\nu$, such that the algorithm performs approximately \lg n + \nu + m multiplications, where $\nu$...
TAOCP 4.6.3 Exercise 10
Each node in the tree represents an exponent $n$, and the tree specifies a parent for each $n$ corresponding to the immediately preceding exponent used to compute $x^n$.
TAOCP 4.6.3 Exercise 11
Let 1=a_0<a_1<\cdots<a_r=n be an addition chain.
TAOCP 4.6.3 Exercise 12
No, it is not possible to extend the tree of Fig.
TAOCP 4.6.3 Exercise 13
We are asked to construct a _star chain_ of length $A+2$ for each of the four cases in Theorem C, thereby showing that Theorem C remains valid when $l$ is replaced by $l^*$.
TAOCP 4.6.3 Exercise 14
Let 1=a_0<a_1<\cdots<a_{r-1}<a_r=n be an addition chain of length
TAOCP 4.6.3 Exercise 15
The reviewer's objections are correct.
TAOCP 4.6.3 Exercise 16
Let $l^{(0)}(n)$ denote the length of an addition chain for $n$ produced by the binary S-and-X method described in Section 4.
TAOCP 4.6.3 Exercise 17
In the proof of Lemma J, the intervals $J_1,\ldots,J_k$ are introduced in order to partition a finite set of admissible values into maximal consecutive blocks.
TAOCP 4.6.3 Exercise 19
Let the multiplicity of an element $x$ in a multiset $A$ be denoted by $m_A(x)$.
TAOCP 4.6.3 Exercise 20
We follow Hansen's **structural decomposition of star chains** as defined in Section 4.
TAOCP 4.6.3 Exercise 21
**Solution to Exercise 4.
TAOCP 4.6.3 Exercise 22
Let $l(n)$ denote the minimum length of an addition chain for $n$, and let $l^F(n)$ denote the length obtained by the factor method.
TAOCP 4.6.3 Exercise 23
Let n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}, \quad p_1 < p_2 < \cdots < p_k be the prime factorization of the positive integer $n$.
TAOCP 4.6.3 Exercise 24
Let R_n(B) = \frac{B^n-1}{B-1} = 1 + B + B^2 + \cdots + B^{\,n-1}.
TAOCP 4.6.3 Exercise 25
Let y=(.
TAOCP 4.6.3 Exercise 26
We wish to compute the $n$th Fibonacci number $F_n$ modulo $m$, where $n$ and $m$ are large integers.
TAOCP 4.6.3 Exercise 27
Let 1 = a_0 < a_1 < \cdots < a_r = n be an addition chain.
TAOCP 4.6.3 Exercise 28
For (a), the smallest $z=x\nabla y$ is obtained by binary addition with carries propagated maximally: at each digit position, $z_j=1$ whenever a $1$ can occur there in some sum $x'+y'$ with $x'\le x$...
TAOCP 4.6.3 Exercise 29
The answer is **yes**.
TAOCP 4.6.3 Exercise 30
Let $n = 31$.
TAOCP 4.6.3 Exercise 31
**Exercise 4.
TAOCP 4.6.3 Exercise 32
Working
TAOCP 4.6.3 Exercise 33
The reviewer's criticism is directed at the proposed response as a _solution_ to Exercise 33.