TAOCP 3.2.2: Other Methods
Section 3.2.2 exercises: 35/36 solved.
Section 3.2.2. Other Methods
Exercises from TAOCP Volume 2 Section 3.2.2: 35/36 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | ▶ [12] | simple | verified | 1m25s |
| 2 | [M20] | math-medium | verified | 1m40s |
| 3 | [23] | medium | verified | 1m29s |
| 4 | [10] | simple | solved | 2m09s |
| 5 | ▶ [20] | medium | verified | 1m01s |
| 6 | [10] | simple | solved | 2m11s |
| 7 | [**] | verified | 2m57s | |
| 8 | [**] | solved | 4m54s | |
| 10 | [**] | verified | 1m15s | |
| 11 | [**] | solved | 4m15s | |
| 12 | ▶ [M28] | math-hard | verified | 3m06s |
| 13 | [M20] | math-medium | solved | 4m54s |
| 14 | [M24] | math-medium | verified | 2m38s |
| 15 | [M27] | math-hard | verified | 1m39s |
| 16 | ▶ [M28] | math-hard | verified | 1m26s |
| 17 | [M33] | math-hard | verified | 3m13s |
| 18 | [M22] | math-medium | solved | 4m27s |
| 19 | [**] | solved | 3m11s | |
| 20 | [**] | solved | 2m01s | |
| 21 | [**] | verified | 1m17s | |
| 22 | ▶ [**] | solved | 2m06s | |
| 23 | [**] | verified | 4m | |
| 24 | [**] | verified | 1m10s | |
| 25 | [**] | verified | 1m23s | |
| 26 | [**] | verified | 1m11s | |
| 27 | [**] | - | - | |
| 28 | [40] | project | verified | 1m27s |
| 29 | ▶ [40] | project | verified | 1m19s |
| 30 | [M37] | math-project | verified | 3m17s |
| 31 | [M30] | math-hard | solved | 5m07s |
| 32 | [M21] | math-medium | verified | 2m29s |
| 33 | ▶ [M23] | math-medium | verified | 1m23s |
| 34 | [M25] | math-medium | verified | 1m12s |
| 35 | [HM35] | hm-hard | verified | 2m48s |
| 36 | [M25] | math-medium | verified | 1m31s |
| 37 | ▶ [HM32] | hm-hard | verified | 1m23s |
TAOCP 3.2.2 Exercise 1
The recurrence U_{n+1}=(aU_n+c/m)\bmod 1 is mathematically equivalent to the linear congruential generator
TAOCP 3.2.2 Exercise 2
Let $m = p_1 p_2 \cdots p_t$, where $p_1, \ldots, p_t$ are distinct primes.
TAOCP 3.2.2 Exercise 3
We first compute the sequences $(X_n)$ and $(Y_n)$ modulo 8, given the recurrences $X_{n+1} = (5X_n + 3) \bmod 8, \quad X_0 = 0,$ $Y_{n+1} = (5Y_n + 1) \bmod 8, \quad Y_0 = 0,$ and $k = 4$.
TAOCP 3.2.2 Exercise 4
Let $m = w \pm 1$ be one of the moduli listed in Table 3.
TAOCP 3.2.2 Exercise 5
Consider Algorithm M as defined in Section 3.
TAOCP 3.2.2 Exercise 6
In the binary method (10), the contents of $X$ form a shift-register sequence determined by a primitive polynomial modulo $2$.
TAOCP 3.2.2 Exercise 7
**Solution.
TAOCP 3.2.2 Exercise 8
**Exercise 3.
TAOCP 3.2.2 Exercise 10
Let $P_e$ be the period of the Fibonacci sequence X_{n+1}=(X_n+X_{n-1})\bmod 2^e.
TAOCP 3.2.2 Exercise 11
Let f(z) = 1 - a_1 z - \cdots - a_k z^k, \qquad G(z) = \frac{1}{f(z)} = \sum_{n \ge 0} A_n z^n.
TAOCP 3.2.2 Exercise 12
We seek integers $X_0, X_1, a, b, c$ such that the sequence X_{n+1} = (a X_n + b X_{n-1} + c) \bmod 2^e, \qquad n \ge 1, has the maximal possible period modulo $2^e$.
TAOCP 3.2.2 Exercise 13
Let $(X_n)$ and $(Y_n)$ be sequences of integers modulo $m$, with least periods $\lambda_1$ and $\lambda_2$, respectively.
TAOCP 3.2.2 Exercise 14
Let $(X_n)$ and $(Y_n)$ be integer sequences modulo $m$ with periods $\lambda_1$ and $\lambda_2$, respectively.
TAOCP 3.2.2 Exercise 15
Algorithm M combines a sequence $(X_n)$ of period length $\lambda_1$ with a sequence of skips $(q_n)$ of period length $\lambda_2$.
TAOCP 3.2.2 Exercise 16
Let $A$ be a $k$-bit word with binary representation $(a_1 a_2 \ldots a_k)_2, \quad a_i \in \{0,1\},$ so that $\text{CONTENTS}(A) = (a_1 a_2 \ldots a_k)_2.$ Consider method (10), which generates a seq...
TAOCP 3.2.2 Exercise 17
Let T_n=(X_{n+k},X_{n+k-1},\ldots,X_{n+1}) \qquad (n\ge0), where $X_1=\cdots=X_k=0$.
TAOCP 3.2.2 Exercise 18
We are asked to show that the sequence of $8$-bit blocks U_n = (X_{8n}, X_{8n+1}, \dots, X_{8n+7}) fails the serial test on pairs, where the $X_n$ are generated by method (10) with $k=35$ and
TAOCP 3.2.2 Exercise 19
Let $X_n=(a_1X_{n-1}+a_2X_{n-2})\bmod p,$ with $k=2$.
TAOCP 3.2.2 Exercise 20
A suitable choice for CONTENTS$(A)$ in method (10) is any $k$-bit binary number in which roughly half of the bits are $0$ and half are $1$.
TAOCP 3.2.2 Exercise 21
Let $m=\prod p_i^{e_i}$ be the prime factorization of $m$.
TAOCP 3.2.2 Exercise 22
Let m=p_1p_2\cdots p_t, where the primes $p_1,\ldots,p_t$ are distinct.
TAOCP 3.2.2 Exercise 23
**Exercise 3.
TAOCP 3.2.2 Exercise 24
Let $\langle Y_n \rangle$ be the sequence with period $2^k - 1$, satisfying $Y_n = (Y_{n-l} + Y_{n-k}) \bmod 2$.
TAOCP 3.2.2 Exercise 25
An alternative to Program A that updates all 55 entries of the $Y$ table every 55th output can be implemented by performing a full sweep of the table instead of a single additive step.
TAOCP 3.2.2 Exercise 26
The conjecture is false in general.
TAOCP 3.2.2 Exercise 28
Exercise 28 asks for an experimental investigation of linear congruential sequences when the modulus is much larger than the machine word size, while the multiplier and increment remain single-precisi...
TAOCP 3.2.2 Exercise 29
**29.
TAOCP 3.2.2 Exercise 30
Let f(x) = x^k - a_1 x^{k-1} - \cdots - a_k be primitive modulo 2, and suppose $X_0, \ldots, X_{k-1}$ are integers not all even.
TAOCP 3.2.2 Exercise 31
We are asked to determine the period length of the sequence $\langle 7^n \rangle$ modulo $m = 2^e > 8$, under the assumption that the initial state $X_0, \dots, X_{54}$ is not all congruent to $\pm 1...
TAOCP 3.2.2 Exercise 32
Let X_n \equiv X_{n-2}+X_{n-55}\pmod m .
TAOCP 3.2.2 Exercise 33
The sequence $\langle X_n \rangle$ satisfies the lagged Fibonacci recurrence $X_n = (X_{n-24} + X_{n-55}) \bmod m, \qquad n \ge 55. \eqno(7)$ Define the generating function $g_n(z) = X_{n+30} + X_{n+2...
TAOCP 3.2.2 Exercise 34
Let M=\begin{pmatrix} 0&1\\ a&c \end{pmatrix},
TAOCP 3.2.2 Exercise 35
**Problem:** Determine the number of pairs $(a,c)\in \mathbb{F}_p \times \mathbb{F}_p$ satisfying the conditions of Exercise 34, i.
TAOCP 3.2.2 Exercise 36
We consider the inversive congruential sequence defined by $X_{n+1} \equiv a X_n^{-1} + c \pmod{2^e}, \qquad e \ge 3, \eqno(1)$ where $a \bmod 4 = 1$ and $c \bmod 4 = 2$.
TAOCP 3.2.2 Exercise 37
Let $T(x)=a x^{-1}+c \pmod p,$ where the value $\infty$ is adjoined in the usual way: $T(0)=\infty,\qquad T(\infty)=c.$ Since the sequence has period $p+1$, the transformation $T$ acts as a single cyc...