TAOCP 3.3.4: The Spectral Test
Section 3.3.4 exercises: 25/32 solved.
Section 3.3.4. The Spectral Test
Exercises from TAOCP Volume 2 Section 3.3.4: 25/32 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [M10] | math-simple | - | - |
| 2 | [HM20] | hm-medium | - | - |
| 3 | [M24] | math-medium | verified | 8m50s |
| 4 | ▶ [M23] | math-medium | - | - |
| 5 | [M30] | math-hard | - | - |
| 6 | [M30] | math-hard | solved | 14m16s |
| 7 | [HM22] | hm-medium | - | - |
| 8 | [M8] | math-simple | - | - |
| 9 | [HM32] | hm-hard | verified | 10m46s |
| 10 | [**] | verified | 4m03s | |
| 11 | ▶ [**] | verified | 4m19s | |
| 12 | [**] | verified | 1m38s | |
| 13 | [**] | solved | 4m43s | |
| 14 | [**] | verified | 3m49s | |
| 15 | ▶ [**] | verified | 1m14s | |
| 16 | [**] | solved | 4m58s | |
| 17 | [**] | verified | 2m38s | |
| 18 | [**] | solved | 2m18s | |
| 19 | [**] | verified | 1m50s | |
| 20 | [M23] | math-medium | verified | 1m31s |
| 21 | [M20] | math-medium | - | - |
| 22 | [M46] | math-research | solved | 3m27s |
| 23 | [M26] | math-hard | verified | 2m08s |
| 24 | ▶ [M28] | math-hard | verified | 5m34s |
| 25 | [HM24] | hm-medium | verified | 5m55s |
| 26 | [M22] | math-medium | solved | 3m33s |
| 27 | [HM39] | hm-project | verified | 3m19s |
| 28 | ▶ [M28] | math-hard | verified | 1m55s |
| 29 | [HM22] | hm-medium | solved | 4m58s |
| 30 | [M33] | math-hard | solved | 3m25s |
| 31 | [M48] | math-research | verified | 4m56s |
| 32 | ▶ [M21] | math-medium | verified | 1m23s |
TAOCP 3.3.4 Exercise 3
Let $b=a-1$.
TAOCP 3.3.4 Exercise 6
Let \frac{m}{a} =[a_0,a_1,\ldots,a_t] be the continued-fraction expansion used in §3.
TAOCP 3.3.4 Exercise 9
Let f(\mathbf{x})=\mathbf{x}^{T}A\mathbf{x}, where $A$ is a positive definite symmetric matrix of order $t$.
TAOCP 3.3.4 Exercise 10
Since $(y_1,y_2)=1$, there exist integers $u_1,u_2$ such that u_1y_2-u_2y_1=m.
TAOCP 3.3.4 Exercise 11
Let m=2^e, \qquad R=\sqrt{\frac43}\,m .
TAOCP 3.3.4 Exercise 12
Let $(u_1,\ldots,u_t)$ be a solution to problem (b) following Eq.
TAOCP 3.3.4 Exercise 13
Let f(x_1,\ldots,x_t)=\sum_{i,j}u_{ij}x_ix_j be a quadratic form.
TAOCP 3.3.4 Exercise 14
Perform Algorithm S by hand for $m=100$, $a=41$, $T=3$.
TAOCP 3.3.4 Exercise 15
Let the hyperplanes defined by $U=(u_1,\ldots,u_t)$ be u_1x_1+\cdots+u_tx_t=h, where $h$ ranges over the integers.
TAOCP 3.3.4 Exercise 16
**Corrected Solution for Exercise 3.
TAOCP 3.3.4 Exercise 17
For each dimension $t$, Algorithm S examines all integer vectors U=(u_1,\ldots,u_t) satisfying (15), and computes
TAOCP 3.3.4 Exercise 18
The solution correctly addresses the exact question.
TAOCP 3.3.4 Exercise 19
Yes.
TAOCP 3.3.4 Exercise 20
Let $X_{n+1} \equiv aX_n \pmod{2^e}, \qquad X_0 \text{ odd}, \qquad a \equiv 3 \text{ or } 5 \pmod 8.$ By exercise 3.
TAOCP 3.3.4 Exercise 22
Let $\mu_2$ and $\mu_3$ denote the two- and three-dimensional spectral constants associated with a linear congruential sequence, as defined in Section 3.
TAOCP 3.3.4 Exercise 23
Let G=(g_{ij})_{1\le i,j\le t}, \qquad g_{ij}=U_i\cdot U_j .
TAOCP 3.3.4 Exercise 24
Let X_n \equiv aX_{n-1}+bX_{n-2}\pmod p, where $p$ is prime, and suppose that the recurrence has period $p^2-1$.
TAOCP 3.3.4 Exercise 25
Let $r(k)$ be defined by Eq.
TAOCP 3.3.4 Exercise 26
Consider a linear congruential sequence $(X_n)$ defined by $X_{n+1} = (a X_n + c) \bmod m, \quad 0 \le X_n < m,$ with full period length $m$.
TAOCP 3.3.4 Exercise 27
Let r(u_1,\ldots,u_t)=\prod_{j=1}^t r(u_j), where, as in equation (46),
TAOCP 3.3.4 Exercise 28
Let X_{n+1}\equiv aX_n \pmod m, where $m$ is prime, $c=0$, $a$ is a primitive root modulo $m$, and $X_0\not\equiv0\pmod m$.
TAOCP 3.3.4 Exercise 29
We are asked to prove that r_{\max} \le \frac{1}{\sqrt{8}\, \nu_t}, where $r_{\max}$ is the maximal value of
TAOCP 3.3.4 Exercise 30
Let $(X_n)$ be a linear congruential sequence modulo $m$, with multiplier $a$ and full period $m$, as in Section 3.