TAOCP 4.5.3: Analysis of Euclid's Algorithm
Section 4.5.3 exercises: 41/42 solved.
Section 4.5.3. Analysis of Euclid's Algorithm
Exercises from TAOCP Volume 2 Section 4.5.3: 41/42 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | ▶ [20] | medium | verified | 3m18s |
| 2 | [M21] | math-medium | verified | 32m23s |
| 3 | [M21] | math-medium | verified | 1m30s |
| 4 | [M20] | math-medium | verified | 41m25s |
| 5 | [**] | verified | 17m39s | |
| 6 | [**] | verified | 23m46s | |
| 7 | [**] | verified | 2m19s | |
| 8 | [**] | verified | 2m12s | |
| 9 | [**] | verified | 1m38s | |
| 10 | [**] | verified | 4m39s | |
| 11 | [**] | verified | 3m19s | |
| 12 | ▶ [**] | verified | 4m24s | |
| 13 | [M40] | math-project | verified | 4m16s |
| 14 | [M22] | math-medium | solved | 5m38s |
| 15 | ▶ [M31] | math-hard | solved | 17m41s |
| 16 | [HM30] | hm-hard | solved | 8m17s |
| 17 | ▶ [M23] | math-medium | solved | 7m45s |
| 18 | [M25] | math-medium | - | - |
| 19 | [M20] | math-medium | solved | 1m50s |
| 20 | [HM20] | hm-medium | solved | 3m37s |
| 21 | [HM20] | hm-medium | verified | 3m46s |
| 22 | [HM46] | hm-research | verified | 4m58s |
| 23 | [HM45] | hm-project | solved | 3m56s |
| 24 | [M22] | math-medium | verified | 2m26s |
| 25 | [HM25] | hm-medium | verified | 1m05s |
| 26 | [M23] | math-medium | solved | 4m08s |
| 27 | [M21] | math-medium | verified | 5m05s |
| 28 | [M23] | math-medium | verified | 1m29s |
| 29 | [M23] | math-medium | verified | 5m57s |
| 30 | ▶ [HM22] | hm-medium | verified | 9m16s |
| 31 | ▶ [M35] | math-hard | verified | 1m53s |
| 32 | [20] | medium | verified | 1m32s |
| 33 | [M32] | math-hard | solved | 6m38s |
| 34 | [HM41] | hm-project | verified | 1m59s |
| 35 | [HM41] | hm-project | verified | 17m37s |
| 36 | [M25] | math-medium | solved | 8m12s |
| 37 | [M38] | math-project | verified | 3m19s |
| 38 | [M35] | math-hard | verified | 7m34s |
| 39 | ▶ [M25] | math-medium | verified | 4m37s |
| 40 | [M28] | math-hard | verified | 2m30s |
| 41 | [M40] | math-project | verified | 5m29s |
| 42 | [M30] | math-hard | verified | 1m55s |
TAOCP 4.5.3 Exercise 1
Let $T(u,v)$ denote the number of MIX division instructions executed by Program 4.
TAOCP 4.5.3 Exercise 2
Let us consider the product $M_n = \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix} \begin{pmatrix}x_1 & 1 \\ 1 & 0\end{pmatrix} \begin{pmatrix}x_2 & 1 \\ 1 & 0\end{pmatrix} \cdots \begin{pmatrix}x_n & 1 \\...
TAOCP 4.5.3 Exercise 3
Let D_n= \det \begin{pmatrix} x_1 & 1 & 0 & \cdots & 0 \\
TAOCP 4.5.3 Exercise 4
Let D_n= K_n(x_1,\ldots,x_n)\,K_n(x_2,\ldots,x_{n+1}) - K_{n+1}(x_1,\ldots,x_{n+1})\,K_{n-1}(x_2,\ldots,x_n).
TAOCP 4.5.3 Exercise 5
Let q_n=K_n(x_1,\ldots,x_n).
TAOCP 4.5.3 Exercise 6
Let X=//B_1,B_2,\ldots//.
TAOCP 4.5.3 Exercise 7
By Euler's description of continuants, $K_n(x_1,\ldots,x_n)$ is the sum of all monomials obtained by deleting disjoint adjacent pairs $x_jx_{j+1}$.
TAOCP 4.5.3 Exercise 8
Let X = [A_0;A_1,A_2,\ldots] be the regular continued fraction generated by the process of §4.
TAOCP 4.5.3 Exercise 9
For (a), write T=//x_{k+1},\ldots,x_n//.
TAOCP 4.5.3 Exercise 10
Let X=A_0+//\!
TAOCP 4.5.3 Exercise 11
Let X=A_0+//\!
TAOCP 4.5.3 Exercise 12
**Exercise 4.
TAOCP 4.5.3 Exercise 13
Let f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 \ne 0 be a polynomial with exactly one real root $\xi > 1$, where $\xi$ is irrational and $f'(\xi) \ne 0$.
TAOCP 4.5.3 Exercise 14
Let X=//a_0,a_1,a_2,\ldots// denote a regular continued fraction.
TAOCP 4.5.3 Exercise 15
We are asked to design an online algorithm that computes the continued fraction y = \frac{ax+b}{cx+d} given the continued fraction
TAOCP 4.5.3 Exercise 16
We define recursively f_0(z) = \tanh z = \frac{e^z - e^{-z}}{e^z + e^{-z}}, \qquad f_{n+1}(z) = \frac{1}{f_n(z)} - \frac{2n+1}{z}.
TAOCP 4.5.3 Exercise 17
We adopt Knuth's notation: //a_1,a_2,\dots,a_n// = \cfrac1{a_1 + \cfrac1{a_2 + \cdots + \cfrac1{a_n}}}.
TAOCP 4.5.3 Exercise 19
Equation (24) is F(x)=\sum_{k\ge1}\left(F\!
TAOCP 4.5.3 Exercise 20
We are asked to deduce equation (38) from equation (37) in _TAOCP_ Volume 2.
TAOCP 4.5.3 Exercise 21
Let $\varphi_c$ be the comparison function obtained by taking T_g(x)=\frac1{x+c}, \qquad c>0.
TAOCP 4.5.3 Exercise 22
We are asked to **develop efficient means to calculate accurate approximations** to the quantities $\lambda_1$ and $\Psi_2(x)$ defined in equation (44) of TAOCP §4.
TAOCP 4.5.3 Exercise 23
**Exercise 4.
TAOCP 4.5.3 Exercise 24
Let $A_n$ denote the $n$th partial quotient in the regular continued fraction expansion of a random real number $x\in(0,1)$, x=[0;A_1,A_2,\ldots].
TAOCP 4.5.3 Exercise 25
We are asked to find a set $\mathcal{I} = I_1 \cup I_2 \cup I_3 \cup \cdots \subseteq [0,1]$, with the $I_k$ disjoint intervals, such that equation (45) does not hold.
TAOCP 4.5.3 Exercise 26
**Exercise 4.
TAOCP 4.5.3 Exercise 27
Let S(M,N)=\sum_{m\le M}\sum_{n\le N}T(m,n).
TAOCP 4.5.3 Exercise 28
Let $1(n)$ denote the constant function $1$, and let $\delta_{n1}$ be $1$ when $n=1$ and $0$ otherwise.
TAOCP 4.5.3 Exercise 29
A rigorous proof cannot be supplied from the information given.
TAOCP 4.5.3 Exercise 30
Let u=qv+r,\qquad 0\le r<v .
TAOCP 4.5.3 Exercise 31
Let the modified algorithm of Exercise 30 be written in the form $u=qv+r,\qquad 0\le r<v,$ and replace the pair $(u,v)$ by $\bigl(v,\min(r,v-r)\bigr).$ Thus each division step uses the remainder of le...
TAOCP 4.5.3 Exercise 32
Associate the positions $1,2,\ldots,n$ with the variables $x_1,x_2,\ldots,x_n$.
TAOCP 4.5.3 Exercise 33
**Exercise 4.
TAOCP 4.5.3 Exercise 34
Let h(n)=\#\{(x,x',y,y'):\ n=xx'+yy',\ x>y>0,\ x'>y'>0,\ x\perp y\}, as in Exercise 33.
TAOCP 4.5.3 Exercise 35
Let S(n)=\sum_{m=1}^{n-1}\sum_{j\ge1}A_j(m/n), where
TAOCP 4.5.3 Exercise 36
We are asked: > What is the smallest value of $u_n$ such that the calculation of $\gcd(u_1, \dots, u_n)$ by Algorithm 4.
TAOCP 4.5.3 Exercise 37
Let $a_1, \ldots, a_n$ be positive integers, and let $K_s(x_1, \ldots, x_n)$ denote the continuant of $n$ variables as defined in equation (4) of Section 4.
TAOCP 4.5.3 Exercise 38
**Statement:** Let L(n) = \max_{m \ge 0} T(m,n), where $T(m,n)$ denotes the number of division steps performed by Algorithm 4.
TAOCP 4.5.3 Exercise 39
Let $h$ be the number of hits and $n$ the number of times at bat.
TAOCP 4.5.3 Exercise 40
Let us consider the infinite binary tree described in the exercise, commonly known as the _Stern–Brocot tree_.
TAOCP 4.5.3 Exercise 41
Let X = \sum_{n\ge 0} \frac{1}{2^{2^n}} = \frac{1}{2} + \frac{1}{4} + \frac{1}{16} + \frac{1}{256} + \cdots.
TAOCP 4.5.3 Exercise 42
Let $X$ be a real number with regular continued fraction expansion X = //A_1, A_2, \ldots// and let $q_n = K_n(A_1, \ldots, A_n)$ denote the $n$-th continuant (denominator of the $n$-th convergent) as...