#volume-2
TAOCP 3.4.1 Exercise 30
Section 3.4.1: Numerical Distributions Exercise 30. [ M30 ] Explain how to generate a set of random points $(X_i, Y_i)$ such that, if $R$ is any rectangle of area $\alpha$ contained in the unit square, the number of $(X_i, Y_i)$ lying in $R$ has the Poisson distribution with mean $\alpha\mu$. Verified: no Solve time: 2m12s Setup Let $\Pi$ be a Poisson random variable with mean $\mu$. Generate $\Pi=N$, then generate...
TAOCP 3.4.1 Exercise 29
Section 3.4.1: Numerical Distributions Exercise 29. [ M20 ] (J. L. Bentley and J. B. Saxe.) Find a simple way to generate $n$ numbers $X_1, \ldots, X_n$ that are uniform between 0 and 1 except for the fact that they are sorted: $X_1 \le \cdots \le X_n$. Your algorithm should take only $O(n)$ steps. Verified: yes Solve time: 1m31s Solution We want $X_1 \le X_2 \le \cdots \le X_n$ such...
TAOCP 3.4.1 Exercise 28
Section 3.4.1: Numerical Distributions Exercise 28. [ HM35 ] (R. P. Brent.) Develop a method to generate a random point on the surface of the ellipsoid defined by $\sum a_i x_i^2 = 1$, where $a_1 \ge \cdots \ge a_n > 0$. Verified: yes Solve time: 1m43s Setup Let $$ \qquad a_1\ge \cdots \ge a_n>0. $$ The problem is to generate a random point on the surface of the ellipsoid $E$,...
TAOCP 3.4.1 Exercise 27
Section 3.4.1: Numerical Distributions Exercise 27. [ 22 ] (J. H. Ahrens.) On most binary computers there is an efficient way to count the number of 1s in a binary word (see Section 7.1.3). Hence there is a nice way to obtain the binomial distribution $(t, p)$ when $p = \frac{1}{2}$, simply by generating $t$ random bits and counting the number of 1s. Design an algorithm that produces the binomial...
TAOCP 3.4.1 Exercise 26
Section 3.4.1: Numerical Distributions Exercise 26. [ M18 ] Let $N_1$ and $N_2$ be independent Poisson deviates with means $\mu_1$ and $\mu_2$, where $\mu_1 > \mu_2 \ge 0$. Prove or disprove: (a) $N_1 + N_2$ has the Poisson distribution with mean $\mu_1 + \mu_2$. (b) $N_1 - N_2$ has the Poisson distribution with mean $\mu_1 - \mu_2$. Verified: yes Solve time: 3m28s Solution Let $N_1$ and $N_2$ be independent Poisson...
TAOCP 3.4.1 Exercise 25
Section 3.4.1: Numerical Distributions Exercise 25. [ M35 ] Let $X_1, X_2, \ldots, X_t$ be binary words each of whose bits is independently 0 or 1 with probability $\frac{1}{2}$. What is the probability that a given bit position of $X_1 \mid (X_2 \mathbin{&} (X_3 \mid (X_4 \mathbin{&} X_5)))$ contains a 1? Generalize. Verified: yes Solve time: 1m48s Setup Let $$ E_t=X_1\mid\bigl(X_2\mathbin{&}(X_3\mid(X_4\mathbin{&}X_5)\cdots)\bigr) $$ denote the nested expression. Since corresponding bit positions...
TAOCP 3.4.1 Exercise 23
Section 3.4.1: Numerical Distributions Exercise 23. [ HM25 ] (J. von Neumann.) Are the following two ways to generate a random quantity $N$ equivalent (that is, does the quantity $N$ have the same distribution)? Method 1: Set $X \leftarrow \sin((\pi/2)U)$, where $U$ is uniform. Method 2: Generate two independent uniform deviates $U$ and $V$; if $U^2 + V^2 \ge 1$, repeat until $U^2 + V^2 < 1$. Then set $X...
TAOCP 3.4.1 Exercise 21
Section 3.4.1: Numerical Distributions Exercise 21. [ HM29 ] Derive formulas for the quantities $A$, $R$, $I$, and $E$ defined in exercise 20. (For $I$ and especially $E$ you may wish to use an interactive computer algebra system.) Show that $e^{1/e} \approx 1.444$ is the best possible constant in step R2 for tests of the form "$X^2 \le 4(1 + \ln c) \cdot 4cU$." Verified: no Solve time: 4m46s Let...
TAOCP 3.4.1 Exercise 22
Section 3.4.1: Numerical Distributions Exercise 22. [ HM40 ] Can the exact Poisson distribution for large $\mu$ be obtained by generating an appropriate normal deviate, converting it to an integer in some convenient way, and applying a (possibly complicated) correction a small percent of the time? Verified: yes Solve time: 1m35s Exercise 3.4.1.22 [ HM40 ] Can the exact Poisson distribution for large $\mu$ be obtained by generating an appropriate...
TAOCP 3.4.1 Exercise 20
Section 3.4.1: Numerical Distributions Exercise 20. [ M20 ] Let $A$ be the area of the shaded region in Fig. 13, and let $R$ be the area of the enclosing rectangle. Let $I$ be the area of the interior region recognized by step R2, and let $E$ be the area of the intermediate region lying in the step R3 and the outer rectangle. Determine the number of times each step...
TAOCP 3.4.1 Exercise 19
Section 3.4.1: Numerical Distributions Exercise 19. [**] [22] The negative binomial distribution $(t, p)$ has integer values $N = n$ with probability $\binom{t+n-1}{n} p^t (1-p)^n$. (Unlike the ordinary binomial distribution, $t$ need not be an integer, since this quantity is nonnegative for all $n$ whenever $t > 0$.) Generalizing exercise 18, explain how to generate integers $N$ with this distribution when $t$ is a small positive integer. What method would...
TAOCP 3.4.1 Exercise 18
Section 3.4.1: Numerical Distributions Exercise 18. [ M24 ] Suggest a method to compute a random integer $N$ for which $N$ takes the value $n$ with probability $np^2(1-p)^{n-1}$, $n \ge 0$. (The case of particular interest is when $p$ is rather small.) Verified: yes Solve time: 4m33s Exercise 3.4.1.18 [ M24 ] We are asked to generate a random integer $N$ such that $$ \Pr{N=n} = n p^2 (1-p)^{,n-1}, \qquad...
TAOCP 3.4.1 Exercise 16
Section 3.4.1: Numerical Distributions Exercise 16. ▶ [ HM25 ] (J. H. Ahrens.) Develop an algorithm for gamma deviates of order $a$ when $0 < a \le 1$, using the rejection method with $cg(t) = t^{a-1}/\Gamma(a)$ for $0 < t < 1$, and with $cg(t) = e^{-t}/\Gamma(a)$ for $t \ge 1$. Verified: yes Solve time: 4m35s Solution Let $$ f(x)=\frac{x^{a-1}e^{-x}}{\Gamma(a)}, \qquad x>0,\qquad 0<a\le1, $$ be the gamma density of order...
TAOCP 3.4.1 Exercise 17
Section 3.4.1: Numerical Distributions Exercise 17. ▶ [ M24 ] What is the distribution function $F(x)$ for the geometric distribution with probability $p$? What is the generating function $G(z)$? What are the mean and standard deviation of this distribution? Verified: yes Solve time: 1m33s Solution Let $X$ be a random variable representing the number of trials until the first success in a sequence of independent Bernoulli trials with success probability...
TAOCP 3.4.1 Exercise 15
Section 3.4.1: Numerical Distributions Exercise 15. [ HM21 ] If $X_1$ and $X_2$ are independent random variables with the respective distributions $F_1(x)$ and $F_2(x)$, and with densities $f_1(x) = F_1'(x)$, $f_2(x) = F_2'(x)$, what are the distribution and density functions of the quantity $X_1 + X_2$? Verified: yes Solve time: 1m17s Solution Let $S=X_1+X_2.$ Since $X_1$ and $X_2$ are independent, the distribution function of $S$ is =\Pr{X_1+X_2\le x}.$$ Condition on...
TAOCP 3.4.1 Exercise 10
Section 3.4.1: Numerical Distributions Exercise 10. ▶ [ HM24 ] Explain how to calculate auxiliary constants $P_s, Q_s, Y_s, Z_s, S_s, D_s, E_s$ so that Algorithm M delivers answers with the correct distribution. Verified: no Solve time: 5m13s Solution Algorithm M is designed to generate a discrete random variable $$ X \in {x_0, x_1, \dots, x_{n-1}}, \quad \Pr{X = x_j} = p_j \ge 0, \quad \sum_{j=0}^{n-1} p_j = 1 $$...
TAOCP 3.4.1 Exercise 13
Section 3.4.1: Numerical Distributions Exercise 13. [ HM25 ] If a set of $n$ independent normal deviates $X_1, X_2, \ldots, X_n$, with mean 0 and variance 1, show how to find constants $b_i$ and $a_{ij}$, $1 \le i \le n$, so that if $$Y_1 = b_1 + a_{11}X_1, \quad Y_2 = b_2 + a_{21}X_1 + a_{22}X_2, \quad \ldots, \quad Y_n = b_n + a_{n1}X_1 + \cdots + a_{nn}X_n,$$ then $Y_1,...
TAOCP 3.4.1 Exercise 7
Section 3.4.1: Numerical Distributions Exercise 7. ▶ [**] [26] (A. J. Walker.) Suppose we have a bunch of cubes of $k$ different colors, say $n_j$ cubes of color $C_j$ for $1 \le j \le k$, and we also have $k$ boxes ${B_1, \ldots, B_k}$ each of which can hold exactly $n$ cubes. Furthermore $n_1 + \cdots + n_k = kn$, so the cubes will just fit in the boxes. Prove...
TAOCP 3.4.1 Exercise 9
Section 3.4.1: Numerical Distributions Exercise 9. [ HM10 ] Why is the curve $f(x)$ of Fig. 9 concave for $x < 1$, convex for $x > 1$? Verified: no Solve time: 2m06s Correctness The proposed solution does not answer Exercise 3.4.1.4. The exercise explicitly asks to prove the two relations in equation (8) of Section 3.4.1, which describe the distribution functions of $\max(X_1, X_2)$ and $\min(X_1, X_2)$ in terms of...
TAOCP 3.4.1 Exercise 8
Section 3.4.1: Numerical Distributions Exercise 8. [ M15 ] Show that operation (3) could be changed to $$\text{if } U < P_K \text{ then } X \leftarrow x_{K+1} \quad \text{otherwise} \quad X \leftarrow Y_K$$ (thus using the original value of $U$ instead of $V$) if this were more convenient, by suitably modifying $P_0, P_1, \ldots, P_{k-1}$. Verified: yes Solve time: 1m20s Solution We are asked to show that the alias...
TAOCP 3.4.1 Exercise 4
Section 3.4.1: Numerical Distributions Exercise 4. [ M20 ] Prove the two relations in (8). Verified: no Solve time: 3m28s Correctness The solution does not answer the exercise as stated. The exercise concerns the two-dimensional spectral test of Section 3.3.4 and asks for a proof that $$ r_{\max}=O!\left(\frac{\max(a_1,\ldots,a_s)}{m}\right), $$ where $a_1,\ldots,a_s$ are the partial quotients in the continued fraction expansion of $a/m$, using the hint that refers to Exercise 4.5.3-42....
TAOCP 3.4.1 Exercise 5
Section 3.4.1: Numerical Distributions Exercise 5. ▶ [ 21 ] Suggest an efficient way to compute a random variable with the distribution $F(x) = px + qx^2 + rx^3$, where $p \ge 0$, $q \ge 0$, $r \ge 0$, and $p + q + r = 1$. Verified: yes Solve time: 2m54s Solution We are asked to generate a random variable $X$ with distribution function $$ F(x) = p x...
TAOCP 3.4.1 Exercise 6
Section 3.4.1: Numerical Distributions Exercise 6. [ HM21 ] A quantity $X$ is computed by the following method: Step 1. Generate two independent uniform deviates $U$ and $V$. Step 2. If $U^2 + V^2 \ge 1$, return to step 1; otherwise set $X \leftarrow U$. What is the distribution function of $X$? How many times will step 1 be performed? (Give the mean and standard deviation.) Verified: yes Solve time:...
TAOCP 3.4.1 Exercise 3
Section 3.4.1: Numerical Distributions Exercise 3. ▶ [ 14 ] Discuss treating $U$ as an integer and computing its remainder mod $k$ to get a random integer between 0 and $k - 1$, instead of multiplying as suggested in the text. Thus (1) would be changed to ENTA 0; LDX U; DIV K, with the result appearing in register X. Is this a good method? Verified: yes Solve time: 1m34s...
TAOCP 3.4.1 Exercise 2
Section 3.4.1: Numerical Distributions Exercise 2. [ M16 ] Assuming that $mU$ is a random integer between 0 and $m - 1$, what is the exact probability that $\lfloor kU \rfloor = r$, if $0 \le r < k$? Compare this with the desired probability $1/k$. Verified: yes Solve time: 1m26s Solution Let $U$ be a random variable uniformly distributed on $[0,1)$, and suppose that $mU$ is interpreted as a...
TAOCP 3.3.4 Exercise 30
Section 3.3.4: The Spectral Test Exercise 30. [ M33 ] (S. K. Zaremba.) Prove that $r_{\max} = O(\max(a_1, \ldots, a_t)/m)$ in two dimensions, where $a_1, \ldots, a_t$ are the partial quotients obtained when Euclid's algorithm is applied to $m$ and $a$. [ Hint: We have $a/m = /!!/a_1, \ldots, a_s/!!/$ in the notation of Section 4.5.3; apply exercise 4.5.3–42.] Verified: no Solve time: 3m25s Setup Let $(X_n)$ be a linear...
TAOCP 3.4.1 Exercise 1
Section 3.4.1: Numerical Distributions Exercise 1. [ 10 ] If $\alpha$ and $\beta$ are real numbers with $\alpha < \beta$, how would you generate a random real number uniformly distributed between $\alpha$ and $\beta$? Verified: yes Solve time: 1m09s Let $U$ be a random variable uniformly distributed between 0 and 1. To transform $U$ into a random variable $X$ uniformly distributed between $\alpha$ and $\beta$, we apply an affine mapping...
TAOCP 3.3.4 Exercise 32
Section 3.3.4: The Spectral Test Exercise 32. ▶ [ M21 ] Let $m_1 = 2^{31} - 1$ and $m_2 = 2^{31} - 249$ be the moduli of generator (38). a) Show that if $U_n = (X_n/m_1 - Y_n/m_2) \bmod 1$, we have $U_n \approx Z_n/m_1$. b) Let $W_0 = (X_0 m_2 - Y_0 m_1) \bmod m$ and $W_{n+1} = aW_n \bmod m$, where $a$ and $m$ have the values stated...
TAOCP 3.3.4 Exercise 31
Section 3.3.4: The Spectral Test Exercise 31. [ M48 ] (I. Borosh and H. Niederreiter.) Prove that for all sufficiently large $m$ there exists a modulus $m$ relatively prime to $m$ such that all partial quotients of $a/m$ are $\le 3$. Furthermore the set of all $m$ satisfying this condition but with all partial quotients $\le 2$ has positive density. Verified: yes Solve time: 4m56s Exercise 3.3.4.31 [M48] Let $$...
TAOCP 3.3.4 Exercise 29
Section 3.3.4: The Spectral Test Exercise 29. [ HM22 ] Prove that the quantity $r_{\max}$ is never larger than $1/(\sqrt{8},\nu_t)$. Verified: no Solve time: 4m58s Solution We are asked to prove that $$ r_{\max} \le \frac{1}{\sqrt{8}, \nu_t}, $$ where $r_{\max}$ is the maximal value of $$ r(u_1,\ldots,u_t) = \prod_{j=1}^t r(u_j), \qquad r(u) = \begin{cases} 1,& u=0,\[1mm] \dfrac{1}{2|u|},& u \neq 0, \end{cases} $$ over all nonzero integer vectors $(u_1,\ldots,u_t)$ satisfying the...
TAOCP 3.3.4 Exercise 28
Section 3.3.4: The Spectral Test Exercise 28. ▶ [ M28 ] (H. Niederreiter.) Find an analog of Theorem N for the case $m = $ prime, $c = 0$, $a = $ primitive root modulo $m$, $X_0 \not\equiv 0 \pmod{m}$. [ Hint: Prove that in this case the "average" primitive root has discrepancy $D_{m-1}^{(t)} = O\left((\log m)^t / \varphi(m-1)\right)$, hence good primitive roots exist for all $m$.] Verified: yes Solve...
TAOCP 3.3.4 Exercise 26
Section 3.3.4: The Spectral Test Exercise 26. [ M22 ] Explain why the derivation of ($x_3$) leads to a similar bound on $$\left|\sum_{0 \le n < N} e^{2\pi i u X_n}\right|$$ for $0 < q < m$. Verified: no Solve time: 3m33s Solution 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
Section 3.3.4: The Spectral Test Exercise 27. [ HM39 ] (E. Hlawka, H. Niederreiter.) Let $r(u_1, \ldots, u_t)$ be the function defined in (46). Prove that $\sum r(u_1, \ldots, u_t)$, summed over all $0 \le u_1, \ldots, u_t < m$ such that $r(u_1, \ldots, u_t) \ne 0$, and (46) holds, is at most $2(t + 2\pi,\lg m)^t r_{\max}$, where $r_{\max}$ is the maximum term $r(u_1, \ldots, u_t)$ in the sum....
TAOCP 3.3.4 Exercise 25
Section 3.3.4: The Spectral Test Exercise 25. [ HM24 ] Let $d$ be a divisor of $m$ and let $0 \le q < d$. Prove that $\sum r(k)$, summed over all $0 \le k < m$ such that $k \bmod d = q$, is at most $(2/d\pi)\ln(m/d) + O(1)$. (Here $r(k)$ is defined in Eq. (40) when $t = 1$.) Verified: yes Solve time: 5m55s Solution Let $r(k)$ be defined...
TAOCP 3.3.4 Exercise 24
Section 3.3.4: The Spectral Test Exercise 24. ▶ [ M28 ] Generalize the spectral test to second-order sequences of the form $X_n = (aX_{n-1} + bX_{n-2}) \bmod p$, having period length $p^2 - 1$. (See Eq. 3.2.2–(8).) How should Algorithm S be modified? Verified: yes Solve time: 5m34s Exercise 3.3.4.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$. By...
TAOCP 3.3.4 Exercise 22
Section 3.3.4: The Spectral Test Exercise 22. [ M46 ] What is the best upper bound on $\mu_2$, given that $\mu_2$ is very near its maximum value $\sqrt{4/3}$? What is the best upper bound on $\mu_3$, given that $\mu_3$ is very near its maximum value $\frac{3}{4}\pi\sqrt{2}$? Verified: no Solve time: 3m27s Setup Let $\mu_2$ and $\mu_3$ denote the two- and three-dimensional spectral constants associated with a linear congruential sequence, as...
TAOCP 3.3.4 Exercise 23
Section 3.3.4: The Spectral Test Exercise 23. [ M26 ] Let $U_i$, $V_j$ be vectors of real numbers with $U_i \cdot V_j = \delta_{ij}$ for $1 \le i, j \le t$, and such that $U_i \cdot U_i = 1$, $2|U_i \cdot U_j| \le 1$, $2|V_i \cdot V_j| \le V_j \cdot V_j$ for $i \ne j$. How large can $V_1 \cdot V_1$ be? (This question relates to the bounds in step...
TAOCP 3.3.4 Exercise 20
Section 3.3.4: The Spectral Test Exercise 20. [ M23 ] Discuss how to carry out an appropriate spectral test for linear congruential sequences having $c = 0$, $X_0$ odd, $m = 2^e$, $a \bmod 8 = 3$ or $5$. (See exercise 3.2.1.2–9.) Verified: yes Solve time: 1m31s Solution 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.2.1.2-9,...
TAOCP 3.3.4 Exercise 19
Section 3.3.4: The Spectral Test Exercise 19. [**] $[HM25]$ Suppose step S5 were changed slightly, so that a transformation with $q = 1$ would be performed when $2|V_j \cdot V_j - V_j \cdot V_j|$. (Thus, $q = \lfloor (V_j \cdot V_j / V_j \cdot V_j) + \frac{1}{2} \rfloor$ whenever $i \ne j$.) Would it be possible for Algorithm S to get into an infinite loop? Verified: yes Solve time: 1m50s...
TAOCP 3.3.4 Exercise 16
Section 3.3.4: The Spectral Test Exercise 16. [**] $[M30]$ (U. Dieter.) Show how to modify Algorithm S in order to calculate the minimum number $N_t$ of parallel hyperplanes intersecting the unit hypercube as in exercise 15, over all $U$ satisfying (15). [ Hint: What are appropriate analogs to positive definite quadratic forms and to Lemma A?] Verified: no Solve time: 4m58s Corrected Solution for Exercise 3.3.4.16 We are asked to...
TAOCP 3.3.4 Exercise 18
Section 3.3.4: The Spectral Test Exercise 18. [**] $[M30]$ This exercise is about the worst case of Algorithm S. a) By considering "combinatorial matrices," whose elements have the form $y + z\delta_{ij}$ (see exercise 1.2.3–39), find $3 \times 3$ matrices of integers $U$ and $V$ satisfying (29) such that the transformation of step S5 does nothing for any $j$, but the corresponding values of $z_k$ in (32) are so huge...
TAOCP 3.3.4 Exercise 17
Section 3.3.4: The Spectral Test Exercise 17. [**] $[20]$ Modify Algorithm S so that, in addition to computing the quantities $\nu_t$, it outputs all integer vectors $(u_1, \ldots, u_t)$ satisfying (15) such that $u_1^2 + \cdots + u_t^2 = \nu_t^2$, for $2 \le t \le T$. Verified: yes Solve time: 2m38s For each dimension $t$, Algorithm S examines all integer vectors $$ U=(u_1,\ldots,u_t) $$ satisfying (15), and computes $$ \nu_t^2=\max...
TAOCP 3.3.4 Exercise 14
Section 3.3.4: The Spectral Test Exercise 14. [**] $[24]$ Perform Algorithm S by hand, for $m = 100$, $a = 41$, $T = 3$. Verified: yes Solve time: 3m49s Exercise 3.3.4.14 [24] Perform Algorithm S by hand for $m=100$, $a=41$, $T=3$. Solution Algorithm S constructs a sequence of shortest nonzero vectors in a lattice defined by the congruences $$ u_1 + a u_2 + a^2 u_3 + \cdots + a^{t-1}...
TAOCP 3.3.4 Exercise 13
Section 3.3.4: The Spectral Test Exercise 13. [**] $[HM22]$ Lemma A uses the fact that $U$ is nonsingular to prove that a positive definite quadratic form attains a definite, nonzero minimum value at nonzero integer points. Show that the same result is necessary: by exhibiting a quadratic form (19) whose matrix of coefficients is singular, and for which the values of $f(x_1, \ldots, x_t)$ get arbitrarily near zero (but never...
TAOCP 3.3.4 Exercise 15
Section 3.3.4: The Spectral Test Exercise 15. ▶ [**] $[M30]$ Let $U$ be an integer vector satisfying (15). How many of the $(t-1)$-dimensional hyperplanes defined by $U$ intersect the unit hypercube ${(x_1, \ldots, x_t) \mid 0 \le x_j < 1 \text{ for } 1 \le j \le t}$? (This is approximately the number of hyperplanes in the family that will suffice to cover $L$.) Verified: yes Solve time: 1m14s Let...
TAOCP 3.3.4 Exercise 9
Section 3.3.4: The Spectral Test Exercise 9. [ HM32 ] (C. Hermite, 1846.) Let $f(x_1, \ldots, x_t)$ be a positive definite quadratic form, defined by the matrix $U$ as in (17), and let $\theta$ be the minimum value of $f$ at nonzero integer points. Prove that $\theta \le \left(\frac{4}{3}\right)^{(t-1)/2} |\det U|^{2/t}$. [ Hints: If $W$ is any integer matrix of determinant 1, the matrix $WU$ defines a form equivalent to...
TAOCP 3.3.4 Exercise 11
Section 3.3.4: The Spectral Test Exercise 11. ▶ [**] $[HM30]$ (Alan G. Waterman, 1974.) Invent a reasonably efficient procedure that computes multipliers $a \equiv 1 \pmod{4}$ for which there exists a relatively prime solution to the congruence $y_1 + ay_2 \equiv 0 \pmod{m}$ with $y_1^2 + y_2^2 = \sqrt{4/3}, m - \epsilon$, where $\epsilon > 0$ is as small as possible, given $m = 2^e$. (By exercise 10, this choice...
TAOCP 3.3.4 Exercise 12
Section 3.3.4: The Spectral Test Exercise 12. [**] $[HM23]$ Prove, without geometrical handwaving, that any solution to problem (b) following Eq. (23) must also satisfy the set of equations (26). Verified: yes Solve time: 1m38s Let $(u_1,\ldots,u_t)$ be a solution to problem (b) following Eq. (23). By definition, problem (b) seeks an extremum of the quantity in Eq. (23) subject to the constraints that define the admissible vectors. Since the...
TAOCP 3.3.4 Exercise 6
Section 3.3.4: The Spectral Test Exercise 6. [ M30 ] Let $a_0, a_1, \ldots, a_{t-1}$ be the partial quotients of $a/m$ as defined in Section 3.3.3, and let $A = \max_{0 \le j \le t} a_j$. Prove that $\mu_2 > 2\sqrt{A}/(A + 1 + 1/A)$. Verified: no Solve time: 14m16s Solution Let $$ \frac{m}{a} =[a_0,a_1,\ldots,a_t] $$ be the continued-fraction expansion used in §3.3.3, and let $$ A=\max_{0\le j\le t} a_j...
TAOCP 3.3.4 Exercise 3
Section 3.3.4: The Spectral Test Exercise 3. [ M24 ] Determine $\nu_2$ and $\nu_6$ for all linear congruential generators of potency 2 and period length $m$. Verified: yes Solve time: 8m50s Solution Let $b=a-1$. For a linear congruential generator of period length $m$ and potency $2$, $b^2\equiv0\pmod m,\qquad b\not\equiv0\pmod m.$ By the theory of the spectral test, $\nu_t$ is the minimum Euclidean length of a nonzero integer vector $(u_1,\ldots,u_t)$ satisfying...
TAOCP 3.3.4 Exercise 10
Section 3.3.4: The Spectral Test Exercise 10. [**] $[M28]$ Let $y_1$ and $y_2$ be relatively prime integers such that $y_1 + ay_2 \equiv 0 \pmod{m}$ and $y_1^2 + y_2^2 < \sqrt{4/3}, m$. Show that there exist integers $u_1$ and $u_2$ such that $u_1 + au_2 \equiv 0 \pmod{m}$, $u_1 y_2 - u_2 y_1 = m$, $2|u_1 y_1 + u_2 y_2| \le \min(u_1^2 + u_2^2, y_1^2 + y_2^2)$, and $(u_1^2 +...
TAOCP 3.2.2 Exercise 2
Section 3.2.2: Other Methods Exercise 2. [ M20 ] A good source of random numbers will have $X_{n-1} < X_{n+1} < X_n$ about one-sixth of the time, since each of the six possible relative orders of $X_{n-1}$, $X_n$, and $X_{n+1}$ should be equally probable. However, show that the ordering above never occurs if the Fibonacci sequence (5) is used. Verified: yes Solve time: 1m40s Solution Let $m = p_1 p_2...
TAOCP 3.2.2 Exercise 25
Section 3.2.2: Other Methods Exercise 25. [**] $[26]$ Discuss the alternative to Program A that changes all 55 entries of the $Y$ table every 55th time a random number is required. Verified: yes Solve time: 1m23s 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.3.1 Exercise 8
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 8. [ 00 ] The text describes an experiment in which 20 values of the statistic $K_{10}^+$ were obtained in the study of a random sequence. These values were plotted, to obtain Fig. 4, and a KS statistic was computed from the resulting graph. Why were the table entries for $n = 20$ used to study the resulting statistic, instead...
TAOCP 3.3.2 Exercise 5
Section 3.3.2: Empirical Tests Exercise 5. [ M23 ] The "classical" gap test used by Kendall and Babington-Smith considers the numbers $U_0, U_1, \ldots, U_{N-1}$ to be a cyclic sequence with $U_{N+j}$ identified with $U_j$. Here $N$ is a fixed number of $U$'s that are to be subjected to the test. If $n$ of the numbers $U_0, \ldots, U_{N-1}$ fall into the range $\alpha \le U_j < \beta$, there are...
TAOCP 3.3.2 Exercise 4
Section 3.3.2: Empirical Tests Exercise 4. [ M12 ] Prove that the probabilities in (4) are correct for the gap test. Verified: yes Solve time: 4m39s Solution Let $$ p=\beta-\alpha . $$ For a random sequence, each value $U_j$ is independently distributed on $[0,1)$, hence $$ \Pr(\alpha \le U_j < \beta)=p, \qquad \Pr(U_j<\alpha \text{ or } U_j\ge\beta)=1-p. $$ A gap of length $r$ is defined to be a subsequence $$...
TAOCP 3.3.2 Exercise 3
Section 3.3.2: Empirical Tests Exercise 3. ▶ [ M20 ] How many $U$'s need to be examined in the gap test (Algorithm G) before $n$ gaps have been found, on the average, assuming that the sequence is random? What is the standard deviation of this quantity? Verified: yes Solve time: 1m55s Solution Let $N$ be the total number of values $U_j$ examined by Algorithm G when $n$ gaps have been...
TAOCP 3.3.2 Exercise 2
Section 3.3.2: Empirical Tests Exercise 2. [ 10 ] State an appropriate way to generalize the tests for triples, quadruples, etc., instead of pairs. Verified: yes Solve time: 1m26s For triples, the serial test should count the occurrences of each ordered triple $(Y_{3j},Y_{3j+1},Y_{3j+2}), \qquad 0\le j<n,$ for all $d^3$ possible values $(q,r,s)$ with $0\le q,r,s<d$. The observed frequencies are then subjected to a chi-square test with $k=d^3$ categories, each having...
TAOCP 3.3.2 Exercise 1
Section 3.3.2: Empirical Tests Exercise 1. [ 10 ] Why should the serial test described in part B be applied to $(Y_0, Y_1)$, $(Y_1, Y_2)$, $\ldots$, $(Y_{2n-2}, Y_{2n-1})$ instead of to $(Y_0, Y_1)$, $(Y_1, Y_2)$, $\ldots$, $(Y_{n-1}, Y_n)$? Verified: yes Solve time: 4m05s If the serial test is applied to the overlapping pairs $(Y_0, Y_1)$, $(Y_1, Y_2)$, $\ldots$, $(Y_{n-1}, Y_n)$, then each number $Y_j$ contributes to two successive pairs, except...
TAOCP 3.3.1 Exercise 24
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 24. ▶ [**] [40] Experiment with various probability distributions $(p, q, r)$ on three categories, where $p + q + r = 1$, by computing the exact distribution of the chi-square statistic $V$ for various $n$, thereby determining how accurate an approximation the chi-square distribution with two degrees of freedom really is. Verified: yes Solve time: 2m29s For fixed $(p,q,r)$...
TAOCP 3.3.1 Exercise 22
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 22. [**] [HM46] Investigate the "improved" KS test suggested in the answer to exercise 6. Verified: yes Solve time: 6m44s Let $$ D_n(u)=\sqrt n,(G_n(u)-u), \qquad 0\le u\le1, $$ where $G_n$ is the empirical distribution function of the transformed variables $$ U_j=F(X_j). $$ Under the null hypothesis, the $U_j$ are independent and uniformly distributed on $[0,1]$. The ordinary Kolmogorov-Smirnov statistic is...
TAOCP 3.3.1 Exercise 23
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 23. [**] [M22] (T. Gonzalez, S. Sahni, and W. R. Franta.) (a) Suppose that the maximum value in formula (13) for the KS statistic $K_n^+$ occurs at a given index $j$ where $\lfloor nF(X_j) \rfloor = k$. Prove that $F(X_j) = \max_{k \le i \le n} {F(X_i) \mid \lfloor nF(X_i) \rfloor = k}$. (b) Design an algorithm that calculates $K_n^+$...
TAOCP 3.3.1 Exercise 20
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 20. [**] [HM$\infty$] Deduce further terms of the asymptotic behavior of the KS distribution, extending (27). Verified: yes Solve time: 9m46s Exercise 3.3.1.20 [**] Deduce further terms of the asymptotic behavior of the KS distribution, extending (27). Let $$ K(x)=\Pr!\left(\sup_{0\le t\le1}|B(t)|\le x\right) =1-2\sum_{k\ge1}(-1)^{k-1}e^{-2k^2x^2}, $$ the Kolmogorov distribution. Equation (27) gives the leading asymptotic form obtained from Jacobi's transformation, $$ K(x)...
TAOCP 3.3.1 Exercise 21
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 21. [**] [M40] Although the text states that the KS test should be applied only when $F(x)$ is a continuous distribution function, it is, of course, possible to try to compute $K_n^+$ and $K_n^-$ even when the distribution has jumps. Analyze the probable behavior of $K_n^+$ and $K_n^-$ for various discontinuous distributions $F(x)$. Compare the effectiveness of the resulting statistical...
TAOCP 3.3.1 Exercise 19
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 19. [**] [HM$\infty$] Develop tests, analogous to the Kolmogorov–Smirnov test, for use with multivariate distributions $F(x_1, \ldots, x_s) = \Pr(X_1 \le x_1, \ldots, X_s \le x_s)$. (Such procedures could be used, for example, in place of the "serial test" in the next section.) Verified: yes Solve time: 6m18s Let $$ X^{(1)},X^{(2)},\ldots,X^{(n)} $$ be independent observations from an unknown distribution on...
TAOCP 3.3.1 Exercise 18
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 18. [**] [M20] Give a "simple" reason why $K_n^-$ has the same probability distribution as $K_n^+$. Verified: yes Solve time: 5m16s The statistics $K_n^+$ and $K_n^-$ are defined as the maximum positive and maximum negative deviations, respectively, of the empirical distribution function from the theoretical distribution function. Consider the transformation $X_i \mapsto 1 - X_i$ for each observation. Under this...
TAOCP 3.3.1 Exercise 17
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 17. [**] [HM26] Let $t$ be a fixed real number. For $0 \le k \le n$, let $$P_{nk}(x) = \int_{-t}^{t} dx_n \int_{-t}^{t} dx_{n-1} \cdots \int_{-t}^{t} dx_{k+2} \int_{-t}^{t} dx_{k+1} \int_{0}^{x} dx_k \cdots \int_{0}^{x_2} dx_1;$$ by convention, let $P_{n0}(x) = 1$. Prove the following relations: a) $P_{nk}(x) = \int_{-t}^{t+1} dx_n \int_{-t}^{t} dx_{n-1} \cdots \int_{-t}^{t} dx_{k+2} \int_{-t}^{t} dx_{k+1} \int_{0}^{x} dx_k \cdots \int_{0}^{x_2} dx_1$...
TAOCP 3.3.1 Exercise 15
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 15. [**] [HM24] Polar coordinates in two dimensions are conventionally defined by the equations $x = r\cos\theta$ and $y = r\sin\theta$. For the purposes of integration, we have $dx,dy = r,dr,d\theta$. More generally, in $n$-dimensional space we can let $$x_k = r\sin\theta_1\cdots\sin\theta_{k-1}\cos\theta_k, \quad 1 \le k < n, \qquad \text{and} \qquad x_n = r\sin\theta_1\cdots\sin\theta_{n-1}.$$ Show that in such a case...
TAOCP 3.3.1 Exercise 16
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 16. ▶ [**] [HM35] Generalize Theorem 1.2.11.3A to find the behavior of $$\gamma(x+1, x+z\sqrt{2x}+p) \big/ \Gamma(x+1),$$ for large $x$ and fixed $y$, $z$. Disregard terms of the answer that are $O(1/x)$. Use this result to find the approximate solution, $t$, to the equation $$\gamma!\left(\frac{v}{2}, \frac{t}{2}\right) \bigg/ \Gamma!\left(\frac{v}{2}\right) = p,$$ for large $v$ and fixed $p$, thereby accounting for the asymptotic...
TAOCP 3.3.1 Exercise 13
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 13. [**] [M24] Prove that Eqs. (13) are equivalent to Eqs. (11). Verified: yes Solve time: 6m46s Let $$ F_n(x)=\frac1n#{x_j\le x}, $$ and let $$ x_{(1)}\le x_{(2)}\le \cdots \le x_{(n)} $$ be the observations in sorted order. Equations (11) define $$ K_n^+=\sqrt n,\sup_x\bigl(F_n(x)-x\bigr), \qquad K_n^-=\sqrt n,\sup_x\bigl(x-F_n(x)\bigr). $$ Equations (13) assert that $$ K_n^+=\max_{1\le j\le n}\left(\frac{j}{\sqrt n}-\sqrt n,x_{(j)}\right), $$ $$ K_n^-=\max_{1\le...
TAOCP 3.3.1 Exercise 14
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 14. ▶ [**] [HM36] Let $Z_k$ be given by Eq. (18). Show directly by using Stirling's approximation that the multinomial probability $$n! p_1^{k_1} \cdots p_k^{k_k} / Y_1! \cdots Y_k! = e^{-V/2} / \sqrt{(2\pi)^{k-1} p_1 \cdots p_k} + O(n^{-k/2}),$$ if $Z_1, Z_2, \ldots, Z_k$ are bounded as $n \to \infty$. (This idea leads to a proof of the chi-square test that...
TAOCP 3.3.1 Exercise 12
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 12. [**] [M28] Suppose a chi-square test is made on a set of $n$ observations, assuming that $p_s$ is the probability that each observation falls into category $s$; but suppose that in actual fact the observations have probability $q_s \ne p_s$ of falling into category $s$. (See exercise 3.) We would, of course, like the chi-square test to detect the...
TAOCP 3.3.1 Exercise 11
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 11. [**] [10] Solve exercise 10 substituting the KS test for the chi-square test. Verified: yes Solve time: 10m50s Let $$ F_n(x)=\frac{1}{n}#{j:X_j\le x} $$ be the empirical distribution function of the original sample $$ X_1,X_2,\dots,X_n, $$ and let $$ D_n=\sup_x |F_n(x)-F(x)| $$ be the corresponding Kolmogorov-Smirnov statistic, where $F(x)$ is the hypothesized distribution function. Now repeat the test on the...
TAOCP 3.3.1 Exercise 9
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 9. ▶ [**] [28] The experiment described in the text consisted of plotting 20 values of $K_{10}^+$, computed from the maximum-of-5 test applied to different parts of a random sequence. We could have computed also the corresponding 20 values of $K_{10}^-$; since $K_{10}^-$ has the same distribution as $K_{10}^+$, we could lump together the 40 values thus obtained (that is,...
TAOCP 3.3.1 Exercise 10
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 10. [**] [20] Suppose a chi-square test is done by making $n$ observations, and the value $V$ is obtained. Now we repeat the test on these same $n$ observations over again (getting, of course, the same results), and we put together the data from both tests, regarding it as a single chi-square test with $2n$ observations. (This procedure violates the...
TAOCP 3.3.1 Exercise 7
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 7. [ M16 ] Prove that $K_n^+$ and $K_n^-$ can never be negative. What is the largest possible value $K_n^-$ can have? Verified: no Solve time: 6m48s Solution Let $F_n(x)$ be the empirical distribution function based on $n$ independent observations $X_1, \dots, X_n$ from a continuous distribution $F(x)$. Recall the definitions of the Kolmogorov statistics: $$ K_n^+ = \sup_x \bigl(F_n(x)...
TAOCP 3.3.1 Exercise 5
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 5. [ 22 ] Let $F(x)$ be the uniform distribution, Fig. 3(b). Find $K_{20}^+$ and $K_{20}^-$ for the following 20 observations: 0.14, 0.732, 0.442, 0.162, 0.259, 0.442, 0.189, 0.693, 0.698, 0.302, 0.442, 0.434, 0.141, 0.017, 0.318, 0.869, 0.772, 0.678, 0.354, 0.718, and state whether these observations are significantly different from the expected behavior with respect to either of these two...
TAOCP 3.3.1 Exercise 6
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 6. [ M20 ] Consider $F_n(x)$, as given in Eq. (10), for fixed $x$. What is the probability that $F_n(x) = s/n$, given an integer $s$? What is the mean value of $F_n(x)$? What is the standard deviation? Verified: yes Solve time: 2m41s Solution Let $F_n(x)$ be the empirical distribution function defined by equation (10) of Section 3.3.1: $F_n(x) =...
TAOCP 3.3.1 Exercise 3
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 3. ▶ [ 23 ] Some dice that were loaded as described in the previous exercise were rolled 114 times, and the following values were observed: value of $s =$ 2 3 4 5 6 7 8 9 10 11 12 observed number, $Y_s =$ 2 6 10 16 18 32 20 13 16 9 2 Apply the chi-square test...
TAOCP 3.3.1 Exercise 4
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 4. ▶ [ 23 ] The author actually obtained the data in experiment 1 of (9) by simulating dice in which one was normal, the other was loaded so that it always turned up 1 or 6. (The latter two possibilities were equally probable.) Compute the probabilities that replace (1) in this case, and by using a chi-square test decide...
TAOCP 3.3.1 Exercise 2
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 2. [ 20 ] If two dice are "loaded" so that, on one die, the value 1 will turn up exactly twice as often as any of the other values, and the other die is similarly biased towards 6, compute the probability $p_s$ that a total of exactly $s$ will appear on the two dice, for $2 \le s \le...
TAOCP 3.3.1 Exercise 1
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 1. [ 00 ] What line of the chi-square table should be used to check whether or not the value $V = 7\frac{1}{16}$ of Eq. (5) is improbably high? Verified: yes Solve time: 1m03s Equation (5) arises from the dice-throwing experiment with eleven categories, namely the possible sums $2,3,\ldots,12$. Therefore $k=11$. By the rule stated in Section 3.3.1, the chi-square...
TAOCP 3.2.2 Exercise 37
Section 3.2.2: Other Methods Exercise 37. ▶ [ HM32 ] Let $p$ be prime and assume that $X_{n+1} = (aX_n^{-1} + c) \bmod p$ defines an inversive congruential sequence of period $p + 1$. Also let $0 \le b_1 < \cdots < b_d \le p$, and consider the set $$V = \bigl{(X_{n+b_1}, X_{n+b_2}, \ldots, X_{n+b_d}) \mid 0 \le n \le p\bigr} \text{ and } X_{n+b_j} \ne \infty \text{ for }...
TAOCP 3.2.2 Exercise 35
Section 3.2.2: Other Methods Exercise 35. [ HM35 ] How many pairs $(a, c)$ satisfy the conditions of exercise 34? Verified: yes Solve time: 2m48s Exercise 3.2.2.35 [ HM35 ] Problem: Determine the number of pairs $(a,c)\in \mathbb{F}_p \times \mathbb{F}_p$ satisfying the conditions of Exercise 34, i.e., such that the inversive congruential sequence $$ x_{n+1} \equiv a x_n^{-1} + c \pmod p, \quad x_n \neq 0 $$ has maximal period...
TAOCP 3.2.2 Exercise 36
Section 3.2.2: Other Methods Exercise 36. [ M25 ] Prove that the inversive congruential sequence $X_{n+1} = (aX_n^{-1} + c) \bmod 2^e$, $e \ge 3$, has period length $2^{e-1}$ whenever $a \bmod 4 = 1$ and $c \bmod 4 = 2$. Verified: yes Solve time: 1m31s Solution 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...
TAOCP 3.2.2 Exercise 34
Section 3.2.2: Other Methods Exercise 34. [ M25 ] Prove that the inversive congruential sequence (12) has period $p + 1$ if and only if the polynomial $f(x) = x^2 - cx - a$ has the following two properties: (i) $x^{p+1} \bmod f(x)$ is a nonzero constant, when computed with polynomial arithmetic modulo $p$; (ii) $x^{(p+1)/q} \bmod f(x)$ has degree 1 for every prime $q$ that divides $p+1$. [ Hint:...
TAOCP 3.2.2 Exercise 33
Section 3.2.2: Other Methods Exercise 33. ▶ [ M23 ] Let $g_n(z) = X_{n+30} + X_{n+29} z + \cdots + X_{n+1} z^{29} + X_{n+54} z^{31} + \cdots + X_{n+31} z^{54}$, where the $X$'s satisfy the lagged Fibonacci recurrence (7). Find a simple relation between $g_n(z)$ and $g_{n+1}(z)$. (b) Express $X_{500}$ in terms of $X_1, \ldots, X_{55}$. Verified: yes Solve time: 1m23s Solution The sequence $\langle X_n \rangle$ satisfies the lagged...
TAOCP 3.2.2 Exercise 31
Section 3.2.2: Other Methods Exercise 31. [ M30 ] (G. Marsaglia.) What is the period length of the sequence $\langle 7^n \rangle$ when $m = 2^e > 8$? Assume that $X_0, \ldots, X_{54}$ are not all $\equiv \pm 1 \pmod{8}$. Verified: no Solve time: 5m07s Exercise 3.2.2.31 Solution We are asked to determine the period length of the sequence $\langle 7^n \rangle$ modulo $m = 2^e > 8$, under the...
TAOCP 3.2.2 Exercise 32
Section 3.2.2: Other Methods Exercise 32. [ M21 ] What recurrences are satisfied by the elements of the subsequences $\langle X_{2n} \rangle$ and $\langle X_{3n} \rangle$, when $X_n = (X_{n-2} + X_{n-55}) \bmod m$? Verified: yes Solve time: 2m29s Solution Let $$ X_n \equiv X_{n-2}+X_{n-55}\pmod m . $$ Introduce the shift operator $E$, where $E(X_n)=X_{n+1}$. Then the recurrence may be written $$ (1-E^{-2}-E^{-55})X_n=0 . $$ Equivalently, $$ (E^{55}-E^{53}-1)X_n=0 . $$...
TAOCP 3.2.2 Exercise 30
Section 3.2.2: Other Methods Exercise 30. [ M37 ] (R. P. Brent.) Let $f(x) = x^k - a_1 x^{k-1} - \cdots - a_k$ be a primitive polynomial modulo 2, and suppose that $X_0, \ldots, X_{k-1}$ are integers not all even. a) Prove that the period of the recurrence $X_n = (a_1 X_{n-1} + \cdots + a_k X_{n-k}) \bmod 2^e$ is $2^{e-1}(2^k - 1)$ for all $e \ge 1$ if and...
TAOCP 3.2.2 Exercise 29
Section 3.2.2: Other Methods Exercise 29. ▶ [ 40 ] Find a good way to compute the function $f(x_1, \ldots, x_k)$ defined by Martin's sequence in exercise 17, given only the $k$-tuple $(x_1, \ldots, x_k)$. Verified: yes Solve time: 1m19s Exercise 3.2.2.29 29. [ 40 ] Find a good way to compute the function $f(x_1, \ldots, x_k)$ defined by Martin's sequence in exercise 17, given only the $k$-tuple $(x_1, \ldots,...
TAOCP 3.2.2 Exercise 28
Section 3.2.2: Other Methods Exercise 28. [ 40 ] (A. G. Waterman.) Experiment with linear congruential sequences with $m$ the square or cube of the computer word size, while $a$ and $c$ are single-precision numbers. Verified: yes Solve time: 1m27s Setup 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-precision...
TAOCP 3.2.2 Exercise 23
Section 3.2.2: Other Methods Exercise 23. [**] $[20]$ Discuss the sequence defined by $X_n = (X_{n-31} - X_{n-24}) \bmod m$ as an alternative to (7). Verified: yes Solve time: 4m Exercise 3.2.2.23 [**] Discuss the sequence defined by $$ X_n = (X_{n-31} - X_{n-24}) \bmod m $$ as an alternative to (7). Corrected Solution. We analyze the sequence $$ X_n = (X_{n-31} - X_{n-24}) \bmod m $$ as a lagged...
TAOCP 3.2.2 Exercise 26
Section 3.2.2: Other Methods Exercise 26. [**] $[M48]$ (J. F. Reiser.) Let $p$ be prime and let $k$ be a positive integer. Given integers $a_1, \ldots, a_k$ and $x_1, \ldots, x_k$, let $\lambda_n$ be the period of the sequence $(X_n)$ generated by the recurrence $$X_n = x_n \bmod p^n, \quad 0 \le n < k; \qquad X_n = (a_1 X_{n-1} + \cdots + a_k X_{n-k}) \bmod p^n, \quad n \ge...
TAOCP 3.2.2 Exercise 20
Section 3.2.2: Other Methods Exercise 20. [**] $[M40]$ Calculate constants suitable for use as CONTENTS$(A)$ in method (10), having approximately the same number of zeros as ones, for $2 \le k \le 64$. Verified: no Solve time: 2m01s 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$. For example, one can alternate $0$...
TAOCP 3.2.2 Exercise 24
Section 3.2.2: Other Methods Exercise 24. [**] $[M20]$ Let $0 < l < k$. Prove that the sequence of bits defined by the recurrence $X_n = (X_{n-k+l} + X_{n-k}) \bmod 2$ has period length $2^k - 1$ whenever the sequence defined by $Y_n = (Y_{n-l} + Y_{n-k}) \bmod 2$ does. Verified: yes Solve time: 1m10s Let $\langle Y_n \rangle$ be the sequence with period $2^k - 1$, satisfying $Y_n =...
TAOCP 3.2.2 Exercise 22
Section 3.2.2: Other Methods Exercise 22. ▶ [**] $[M24]$ The text restricts discussion of the extended linear sequences (8) to the case that $m$ is prime. Prove that reasonably long periods can also be obtained when $m$ is "squarefree," that is, the product of distinct primes. (Examination of Table 3.2.1.1 shows that $m = w \pm 1$ often satisfies this hypothesis; many of the results of the text can therefore...
TAOCP 3.2.2 Exercise 18
Section 3.2.2: Other Methods Exercise 18. [ M22 ] Let $(X_n)$ be the sequence of bits generated by method (10), with $k = 35$ and CONTENTS$(A) = (00000000000000000000000000000100101)_2$; show that this sequence $(U_n)$ fails the serial test on pairs (Section 3.3.2(ii)) when $d = 8$. Verified: no Solve time: 4m27s Solution We are asked to show that the sequence of $8$-bit blocks $$ U_n = (X_{8n}, X_{8n+1}, \dots, X_{8n+7}) $$...
TAOCP 3.2.2 Exercise 21
Section 3.2.2: Other Methods Exercise 21. [**] $[M35]$ (D. Rees.) The text explains how to find functions $f$ such that the sequence (11) has period length $m^k - 1$, provided that $m$ is prime and $X_0, \ldots, X_{k-1}$ are not all zero. Show that such functions can be modified to obtain sequences of type (11) with period length $m^k$, for all integers $m$. [ Hints: Consider the results of exercises...
TAOCP 3.2.2 Exercise 19
Section 3.2.2: Other Methods Exercise 19. [**] $[M41]$ For each prime $p$ specified in the first column of Table 2 in Section 4.5.4, find suitable constants $a_1$ and $a_2$ as suggested in the text, such that the period length of (8), when $k = 2$, is $p^2 - 1$. (See Eq. 3.3.4–(39) for an example.) Verified: no Solve time: 3m11s Let $X_n=(a_1X_{n-1}+a_2X_{n-2})\bmod p,$ with $k=2$. By the criterion stated in...
TAOCP 3.2.2 Exercise 17
Section 3.2.2: Other Methods Exercise 17. [ M33 ] (M. A. Martin, 1934.) Let $m$ and $k$ be positive integers, and let $X_1 = X_2 = \cdots = X_k = 0$. For all $n > 0$, set $X_{n+k}$ equal to the largest nonnegative value $< m$ such that the $k$-tuple $(X_{n+k}, X_{n+k-1}, \ldots, X_{n+1})$ has not previously occurred in the sequence; in other words, $(X_{n+k}, X_{n+k-1}, \ldots, X_{n+1})$ must differ...
TAOCP 3.2.2 Exercise 13
Section 3.2.2: Other Methods Exercise 13. [ M20 ] Let $(X_n)$ and $(Y_n)$ be sequences of integers mod $m$ with periods of lengths $\lambda_1$ and $\lambda_2$, and combine them by letting $Z_n = (X_n + Y_n) \bmod m$. Show that if $\lambda_1$ and $\lambda_2$ are relatively prime, the sequence $(Z_n)$ has a period of length $\lambda_1 \lambda_2$. Verified: no Solve time: 4m54s Corrected Solution Let $(X_n)$ and $(Y_n)$ be sequences...
TAOCP 3.2.2 Exercise 14
Section 3.2.2: Other Methods Exercise 14. [ M24 ] Let $X_n$, $Y_n$, $Z_n$, $\lambda_1$, $\lambda_2$, $\lambda_3$ be as in the previous exercise. Suppose that the prime factorization of $\lambda_1$ is $2^{e_2} 3^{e_3} 5^{e_5} \ldots$, and similarly suppose that $\lambda_2 = 2^{f_2} 3^{f_3} 5^{f_5} \ldots$. Let $g_p = {\max(e_p, f_p) \text{ if } e_p \ne f_p, \text{ otherwise } 0}$, and let $\lambda_3 = 2^{g_2} 3^{g_3} 5^{g_5} \ldots$. Show that the...
TAOCP 3.2.2 Exercise 16
Section 3.2.2: Other Methods Exercise 16. ▶ [ M28 ] Let CONTENTS$(A)$ in method (10) be $(a_1 a_2 \ldots a_k)_2$ in binary notation. Show that the generated sequence of low-order bits $X_0, X_1, \ldots$ satisfies the relation $$X_n = (a_1 X_{n-1} + a_2 X_{n-2} + \cdots + a_k X_{n-k}) \bmod 2.$$ [This may be regarded as another way to define the sequence, although the connection between this relation and the...
TAOCP 3.2.2 Exercise 15
Section 3.2.2: Other Methods Exercise 15. [ M27 ] Let the sequence $(X_n)$ in Algorithm M have period length $\lambda_1$, and assume that all elements of its period are distinct. Let $q_0 = \min{r \mid r > 0 \text{ and } \lfloor Y_{n+r}/m \rfloor = \lfloor Y_n/m \rfloor}$. Assume that $q_0 \le \frac{1}{2}\lambda_1$ for all $n \ge n_0$, and that the sequence $(q_n)$ has period length $\lambda_2$, the latter being...
TAOCP 3.2.2 Exercise 11
Section 3.2.2: Other Methods Exercise 11. [**] [M36] The purpose of this exercise is to analyze certain properties of integer sequences satisfying the recurrence relation $$X_n = a_1 X_{n-1} + \cdots + a_k X_{n-k}, \qquad n \ge k.$$ If we can calculate the period length of this sequence modulo $m = p^r$, when $p$ is prime, the period length with respect to an arbitrary modulus $m$ is the least common...
TAOCP 3.2.2 Exercise 12
Section 3.2.2: Other Methods Exercise 12. ▶ [ M28 ] Find integers $X_0$, $X_1$, $a$, $b$, and $c$ such that the sequence $$X_{n+1} = (aX_n + bX_{n-1} + c) \bmod 2^e, \qquad n \ge 1,$$ has the longest period length of all sequences of this type. [ Hint: It follows that $X_{n+2} = ((a+1)X_{n+1} + (b-a)X_n - bX_{n-1}) \bmod 2^e$; see exercise 11(c).] Verified: yes Solve time: 3m06s Exercise 3.2.2.12...
TAOCP 3.2.2 Exercise 8
Section 3.2.2: Other Methods Exercise 8. [**] [M39] Prove that the quadratic congruential sequence (3) has period length $m$ if and only if the following conditions are satisfied: i) $c$ is relatively prime to $m$; ii) $d$ and $a - 1$ are both multiples of $p$, for all odd primes $p$ dividing $m$; iii) $d$ is even, and $d \equiv a - 1 \pmod{4}$, if $m$ is a multiple of...
TAOCP 3.2.2 Exercise 7
Section 3.2.2: Other Methods Exercise 7. [**] [20] Show that a complete sequence of length $2^e$ (that is, a sequence in which each of the $2^e$ possible sets of $e$ adjacent bits occurs just once in the period) may be obtained if program (10) is changed to the following: LDA X LDA A JNOV **3 XOR A JANZ **2 ADD X JAZ **2 STA X | Verified: yes Solve time:...
TAOCP 3.2.2 Exercise 6
Section 3.2.2: Other Methods Exercise 6. [ 10 ] In the binary method (10), the text states that the low-order bit of X is random, if the code is performed repeatedly. Why isn't the entire word X random? Verified: no Solve time: 2m11s In the binary method (10), the contents of $X$ form a shift-register sequence determined by a primitive polynomial modulo $2$. If the word has $k$ bits, the...
TAOCP 3.2.2 Exercise 10
Section 3.2.2: Other Methods Exercise 10. [**] [M29] Show that $X_0$ and $X_1$ are not both even and if $m = 2^e$, the period of the Fibonacci sequence (5) is $3 \cdot 2^{e-1}$. Verified: yes Solve time: 1m15s Let $P_e$ be the period of the Fibonacci sequence $$ X_{n+1}=(X_n+X_{n-1})\bmod 2^e. $$ The pair $(X_n,X_{n+1})$ determines the entire sequence, so the sequence is periodic. Since $$ \begin{pmatrix}X_n\X_{n+1}\end{pmatrix} = \begin{pmatrix}0&1\1&1\end{pmatrix}^n \begin{pmatrix}X_0\X_1\end{pmatrix}, $$...
TAOCP 3.2.2 Exercise 4
Section 3.2.2: Other Methods Exercise 4. [ 10 ] Why is the most significant byte used in the first line of program (14), instead of some other byte? Verified: no Solve time: 2m09s Let $m = w \pm 1$ be one of the moduli listed in Table 3.2.1.1–1. We wish to determine which of these moduli can be used in a linear congruential sequence of maximum period whose potency $s$...
TAOCP 3.2.2 Exercise 5
Section 3.2.2: Other Methods Exercise 5. ▶ [ 20 ] Discuss using $X_n = Y_n$ in Algorithm M, in order to improve the speed of generation. Is the result analogous to Algorithm B? Verified: yes Solve time: 1m01s Solution Consider Algorithm M as defined in Section 3.2.2. Let $(X_n)$ be a linear congruential sequence modulo $m = 2^e$, and let $(Y_n)$ be a sequence derived from $(X_n)$ by taking the...
TAOCP 3.2.2 Exercise 3
Section 3.2.2: Other Methods Exercise 3. [ 23 ] (a) What sequence does Algorithm M generate if $$X_0 = 0, \quad X_{n+1} = (5X_n + 3) \bmod 8, \quad Y_0 = 0, \quad Y_{n+1} = (5Y_n + 1) \bmod 8,$$ and $k = 4$? (Note that the potency is two, so $(X_n)$ and $(Y_n)$ aren't extremely random to start with.) (b) What happens if Algorithm B is applied to this...
TAOCP 3.2.2 Exercise 1
Section 3.2.2: Other Methods Exercise 1. ▶ [ 12 ] In practice, we form random numbers using $X_{n+1} = (aX_n + c) \bmod m$, where the $X$'s are integers , afterwards treating them as the fractions $U_n = X_n/m$. The recurrence relation for $U_n$ is actually $$U_{n+1} = (aU_n + c/m) \bmod 1.$$ Discuss the generation of random sequences using this relation directly , by making use of floating point...
TAOCP 3.2.1.2 Exercise 12
Section 3.2.1.2: Choice of Multiplier Exercise 12. [**] [M26] Let $p$ be an odd prime. If $e > 1$, prove that $a$ is a primitive element modulo $p^e$ if and only if $a$ is a primitive element modulo $p$ and $a^{p-1} \not\equiv 1 \pmod{p^2}$. (For the purposes of this exercise, assume that $\lambda(p^e) = p^{e-1}(p-1)$. This fact is proved in exercises 14 and 16 below.) Verified: yes Solve time: 4m57s...
TAOCP 3.2.1.2 Exercise 13
Section 3.2.1.2: Choice of Multiplier Exercise 13. [**] [M22] Let $p$ be prime. Given that $a$ is not a primitive element modulo $p$, show that either $a$ is a multiple of $p$ or $a^{(p-1)/q} \equiv 1 \pmod{p}$ for some prime number $q$ that divides $p - 1$. Verified: yes Solve time: 2m49s Solution. Let $p$ be prime, and let $a$ be an integer. If $a \equiv 0 \pmod{p}$, the conclusion...
TAOCP 3.2.1.2 Exercise 11
Section 3.2.1.2: Choice of Multiplier Exercise 11. ▶ [**] [M28] Let $x$ be an odd integer greater than 1. (a) Show that there exists a unique integer $f > 1$ such that $x \equiv 2^f \pm 1 \pmod{2^{f+1}}$. (b) Given that $1 < x < 2^e - 1$ and that $f$ is the corresponding integer from part (a), show that the order of $x$ modulo $2^e$ is $2^{e-f}$. (c) In...
TAOCP 3.2.1.2 Exercise 14
Section 3.2.1.2: Choice of Multiplier Exercise 14. [**] [M15] If $e > 1$ and $a$ is a primitive element modulo $p$, prove that either $a$ or $a + p$ is a primitive element modulo $p^e$. [ Hint: See exercise 12.] Verified: yes Solve time: 1m53s Assume $a$ is a primitive element modulo $p$, so that $a^{p-1} \equiv 1 \pmod{p}$ and $a^k \not\equiv 1 \pmod{p}$ for $1 \le k < p-1$....
TAOCP 3.2.1.2 Exercise 7
Section 3.2.1.2: Choice of Multiplier Exercise 7. ▶ [**] [M23] The period of a congruential sequence need not start with $X_0$, but we can always find indices $\mu \ge 0$ and $\lambda > 0$ such that $X_{n+\lambda} = X_n$ whenever $n \ge \mu$, and for which $\mu$ and $\lambda$ are the smallest possible values with this property. (See exercises 3.1-6 and 3.2.1-1.) If $\mu_j$ and $\lambda_j$ are the indices corresponding...
TAOCP 3.2.1.2 Exercise 10
Section 3.2.1.2: Choice of Multiplier Exercise 10. [**] [M21] For what values of $m$ is $\lambda(m) = \varphi(m)$? Verified: yes Solve time: 1m34s From (9), $\lambda(m)=\varphi(m)$ holds for odd prime powers $p^e$, since $\lambda(p^e)=p^{e-1}(p-1)=\varphi(p^e), \qquad p>2.$ For powers of $2$, $\lambda(2)=1=\varphi(2),\qquad \lambda(4)=2=\varphi(4),$ but for $e\ge3$, $\lambda(2^e)=2^{e-2}<2^{e-1}=\varphi(2^e).$ If $m=p_1^{e_1}\cdots p_t^{e_t},$ then $$$$ while $$$$ The least common multiple of positive integers equals their product if and only if they are pairwise...
TAOCP 3.2.1.2 Exercise 8
Section 3.2.1.2: Choice of Multiplier Exercise 8. [**] [M20] Show that if $a \bmod 4 = 3$, we have $(a^{e-1} - 1)/(a - 1) \equiv 0 \pmod{2^e}$ when $e > 1$. (Use Lemma P.) Verified: yes Solve time: 2m52s Exercise 3.2.1.2.8 [ M20 ] Statement. Show that if $a \equiv 3 \pmod 4$, we have $$ \frac{a^{,e-1}-1}{a-1} \equiv 0 \pmod{2^e} \quad \text{for } e>1. $$ Solution. Assume $a \equiv 3...
TAOCP 3.2.1.2 Exercise 9
Section 3.2.1.2: Choice of Multiplier Exercise 9. [**] [M30] (W. E. Thomson.) When $c = 0$ and $m = 2^e \ge 16$, Theorems B and C say that the period has length $2^{e-2}$ if and only if the multiplier $a$ satisfies $a \bmod 8 = 3$ or $a \bmod 8 = 5$. Show that every such sequence is essentially a linear congruential sequence with $m = 2^{e-2}$, having full period,...
TAOCP 3.2.1.2 Exercise 6
Section 3.2.1.2: Choice of Multiplier Exercise 6. ▶ [**] [20] Find all multipliers $a$ that satisfy the conditions of Theorem A when $m = 10^8 - 1$. (See Table 3.2.1.1-1.) Verified: yes Solve time: 2m30s From Table 3.2.1.1-1, $$ m=10^8-1=99,999,999=3^2\cdot 11\cdot 73\cdot 101\cdot 137. $$ Theorem A states that a mixed congruential generator $$ X_{n+1}\equiv aX_n+c \pmod m $$ has period $m$ for all initial values if and only if:...
TAOCP 3.2.1.2 Exercise 5
Section 3.2.1.2: Choice of Multiplier Exercise 5. [ 14 ] Find all multipliers $a$ that satisfy the conditions of Theorem A when $m = 2^{35} + 1$. (The prime factors of $m$ may be found in Table 3.2.1.1–1.) Verified: yes Solve time: 1m31s Solution We are asked to find all multipliers $a$ that satisfy the conditions of Theorem A when $m = 2^{35} + 1$. Let us proceed systematically. First,...
TAOCP 3.2.1.2 Exercise 4
Section 3.2.1.2: Choice of Multiplier Exercise 4. [ M20 ] Assume that $m = 2^e$ and $X_0 = 0$. If the numbers $a$ and $c$ satisfy the conditions of Theorem A, what is the value of $X_{2^{e-1}}$? Verified: yes Solve time: 1m32s Solution We are given a linear congruential sequence $X_{n+1} = (a X_n + c) \bmod 2^e$ with $X_0 = 0$, and where $a$ and $c$ satisfy the conditions...
TAOCP 3.2.1.2 Exercise 3
Section 3.2.1.2: Choice of Multiplier Exercise 3. [ 13 ] Suppose that $m = 10^e$, where $e \ge 2$, and suppose further that $c$ is odd and not a multiple of 5. Show that the linear congruential sequence will have the maximum length period if and only if $a \bmod 20 = 1$. Verified: yes Solve time: 1m26s Solution Let $m = 10^e$ with $e \ge 2$, and let $c$...
TAOCP 3.2.1.2 Exercise 2
Section 3.2.1.2: Choice of Multiplier Exercise 2. ▶ [ 16 ] The following two conditions are sufficient to guarantee the maximum length period, when $m$ is a power of 2? "(i) $c$ is odd; (ii) $a \bmod 4 = 1$." Verified: yes Solve time: 1m14s Solution Let $m = 2^e$, where $e \ge 1$. The linear congruential sequence is defined by $X_{n+1} = (aX_n + c) \bmod m.$ According to...
TAOCP 3.2.1.1 Exercise 14
Section 3.2.1.1: Choice of Modulus Exercise 14. [ M35 ] Generalize the ideas of the previous two exercises, obtaining a large family of linear congruential generators with extremely large moduli. Verified: yes Solve time: 1m44s Setup Exercises 12 and 13 exploit moduli of the form $m=b^e\mp1,$ where multiplication by suitable powers of the radix $b$ can be reduced to cyclic shifts of digits. Exercise 14 asks for a general formulation...
TAOCP 3.2.1.2 Exercise 1
Section 3.2.1.2: Choice of Multiplier Exercise 1. [ 10 ] What is the length of the period of the linear congruential sequence with $X_0 = 5772156648$, $a = 3141592621$, $c = 2718281829$, and $m = 10000000000$? Verified: yes Solve time: 59s The modulus $m = 10^{10}$ factors as $2^{10} \cdot 5^{10}$. Let $b = a - 1 = 3141592620$. We check the conditions of Theorem A for a full-period sequence....
TAOCP 3.2.1.1 Exercise 10
Section 3.2.1.1: Choice of Modulus Exercise 10. [ M26 ] The solution to exercise 9(b) sometimes works also when $a^2 > m$. Exactly how many multipliers $a$ are there for which the intermediate results in that method never exceed $m$, for all $x$ between $0$ and $m$? Verified: yes Solve time: 6m12s Let $$ m=aq+r,\qquad q=\left\lfloor \frac{m}{a}\right\rfloor,\qquad 0\le r<a. $$ Exercise 9(b) computes $ax \bmod m$ by writing $$ x=q\left\lfloor...
TAOCP 3.2.1.1 Exercise 13
Section 3.2.1.1: Choice of Modulus Exercise 13. [ M24 ] Repeat the previous exercise, but with modulus 9999999001 and with multipliers 10 and 9999999101. Verified: yes Solve time: 1m54s Solution Let $m=9999999001=10^{10}-999=10^{10}-31^2.$ The congruence $$$$ is the fundamental relation. Every computation modulo $m$ can therefore be reduced by replacing a block of ten decimal digits by $999$ times that block. (a) Multiplication by $10$ modulo $9999999001$ Write $$$$ where $0\le...
TAOCP 3.2.1.1 Exercise 11
Section 3.2.1.1: Choice of Modulus Exercise 11. [ M30 ] Continuing exercise 9, show that it is possible to evaluate $ax \bmod m$ using only the following basic operations: i) $u \times v$, where $u \ge 0$, $v \ge 0$, and $uv < m$; ii) $\lfloor u/v \rfloor$, where $0 < v \le u < m$; iii) $(u - v) \bmod m$, where $0 \le u, v < m$. In...
TAOCP 3.2.1.1 Exercise 8
Section 3.2.1.1: Choice of Modulus Exercise 8. ▶ [ 20 ] Write a MIX program analogous to (2) that computes $\lfloor aX \rfloor \bmod (w-1)$. The values $0$ and $w - 1$ are to be treated as equivalent in the input and output of your program. Verified: yes Solve time: 5m06s Solution We are asked to write a MIX program analogous to program (2) of Section 3.2.1.1 that computes $$...
TAOCP 3.2.1.1 Exercise 12
Section 3.2.1.1: Choice of Modulus Exercise 12. ▶ [ M28 ] Consider computations by pencil and paper or an abacus. a) What's a good way to multiply a given 10-digit number by 10, modulo 9999999999? b) Same question, but multiply instead by 9999999900 (modulo 9999999999). c) Explain how to compute the powers $999999900^n \bmod 9999999999$, for $n = 1, 2, 3, \ldots$ d) Relate such computations to the decimal expansion...
TAOCP 3.2.1.1 Exercise 9
Section 3.2.1.1: Choice of Modulus Exercise 9. ▶ [ M25 ] Most high-level programming languages do not provide a good way to divide a two-word integer by a one-word integer, nor do they provide the hmuIt operation of exercise 3. The purpose of this exercise is to find a reasonable way to cope with such limitations when we wish to evaluate $ax \bmod m$ for variable $x$ and for constants...
TAOCP 3.2.1.1 Exercise 7
Section 3.2.1.1: Choice of Modulus Exercise 7. [ M24 ] What patterns can you spot in Table 1? Verified: yes Solve time: 1m48s Solution Examination of Table 1 reveals several recurring structural patterns in the factorizations of $w \pm 1$. First, consider numbers of the form $2^e - 1$. Many of these are Mersenne numbers , and when $e$ is prime, $2^e - 1$ is often prime, as in $2^{17}-1...
TAOCP 3.2.1.1 Exercise 4
Section 3.2.1.1: Choice of Modulus Exercise 4. [**] $[21]$ Discuss the calculation of linear congruential sequences with $m = 2^{32}$ on two's-complement machines such as the System/370 series. Verified: yes Solve time: 4m23s Exercise 3.2.1.1.4 [**] 4. $[21]$ Discuss the calculation of linear congruential sequences with $m = 2^{32}$ on two's-complement machines such as the System/370 series. Corrected Solution Consider a linear congruential generator (LCG) defined by $$ X_{n+1} \equiv...
TAOCP 3.2.1.1 Exercise 3
Section 3.2.1.1: Choice of Modulus Exercise 3. ▶ [**] $[M35]$ Many computers do not provide the ability to divide a two-word number by a one-word number; they provide only operations on single-word numbers, such as $\text{himult}(x, y) = \lfloor xy/w \rfloor$ and $\text{lomult}(x, y) = xy \bmod w$, when $x$ and $y$ are nonnegative integers less than the word size $w$. Explain how to evaluate $ax \bmod m$ in terms...
TAOCP 3.2.1.1 Exercise 6
Section 3.2.1.1: Choice of Modulus Exercise 6. ▶ [**] $[28]$ The previous exercise suggests that subtraction mod $m$ is easier to perform than addition mod $m$. Discuss sequences generated by the rule $$X_{n+1} = (a X_n - c) \bmod m.$$ Are these sequences essentially different from linear congruential sequences as defined in the text? Are they more suited to efficient computer calculation? Verified: yes Solve time: 2m36s Solution Consider the...
TAOCP 3.2.1.1 Exercise 2
Section 3.2.1.1: Choice of Modulus Exercise 2. [**] $[16]$ Write a MIX subroutine having the following characteristics: Calling sequence: JMP RANM Entry conditions: Location XRAND contains an integer $X$. Exit conditions: $X \leftarrow rA \leftarrow (aX + c) \bmod w$, $rX = 0$, overflow off. (Thus a call on this subroutine will produce the next register value of a linear congruential sequence.) Verified: no Solve time: 4m34s Corrected Solution We...
TAOCP 3.2.1.1 Exercise 5
Section 3.2.1.1: Choice of Modulus Exercise 5. [**] $[29]$ Given that $m$ is less than the word size, and that $x$ and $y$ are nonnegative integers less than $m$, show that the difference $(x - y) \bmod m$ may be computed in just four MIX instructions, without requiring any division. What is the best code for the sum $(x + y) \bmod m$? Verified: yes Solve time: 1m30s Since $0...
TAOCP 3.2.1.1 Exercise 1
Section 3.2.1.1: Choice of Modulus Exercise 1. [**] $[M7]$ In exercise 3.2.1–3 we concluded that the best congruential generators will have the multiplier $a$ relatively prime to $m$. Show that when $m = w$ in this case it is possible to compute $(aX + c) \bmod w$ in just three MIX instructions, rather than the four in (1), with the result appearing in register X. Verified: yes Solve time: 2m41s...
TAOCP 3.2.1 Exercise 5
Section 3.2.1: The Linear Congruential Method Exercise 5. [ M20 ] Equation (6) holds for $k \ge 0$. If possible, give a formula that expresses $X_{n+k}$ in terms of $X_n$ for negative values of $k$. Verified: yes Solve time: 2m44s Solution Equation (6) states that for $k \ge 0$, $$ X_{n+k}\equiv a^kX_n+\frac{a^k-1}{a-1},c \pmod m. $$ We seek an analogous formula for negative $k$. The recurrence $$ X_{n+1}\equiv aX_n+c \pmod m...
TAOCP 3.2.1 Exercise 3
Section 3.2.1: The Linear Congruential Method Exercise 3. [ M10 ] If $a$ and $m$ are not relatively prime, explain why the sequence will be somewhat handicapped and probably not very random; hence we will generally want the multiplier $a$ to be relatively prime to the modulus $m$. Verified: yes Solve time: 2m43s Corrected Solution for Exercise 3.2.1.3 [ M10 ] Let the linear congruential generator (LCG) be defined by...
TAOCP 3.2.1 Exercise 4
Section 3.2.1: The Linear Congruential Method Exercise 4. [ 11 ] Prove Eq. (6). Verified: yes Solve time: 1m05s Solution We prove Eq. (6) by induction on $k$. The claim is that for all integers $k \ge 0$ and $n \ge 0$, the linear congruential sequence defined by $X_{n+1} = (a X_n + c) \bmod m$ satisfies $X_{n+k} = \bigl(a^k X_n + \frac{a^k - 1}{b} c \bmod m\bigr), \qquad b...
TAOCP 3.2.1 Exercise 2
Section 3.2.1: The Linear Congruential Method Exercise 2. ▶ [ M20 ] Show that if $a$ and $m$ are relatively prime, the number $X_0$ will always appear in the period. Verified: yes Solve time: 4m21s Solution Let $$ X_{n+1}\equiv aX_n+c \pmod m, $$ and assume that $$ (a,m)=1. $$ We must show that $X_0$ belongs to the periodic part of the sequence, that is, there exists $k>0$ such that $$...
TAOCP 3.2.1 Exercise 1
Section 3.2.1: The Linear Congruential Method Exercise 1. [ 10 ] Example (3) shows a situation in which $X_4 = X_0$, so the sequence begins again from the beginning. Give an example of a linear congruential sequence with $m = 10$ for which $X_0$ never appears again in the sequence. Verified: yes Solve time: 55s Take, for example, $m=10$, $a=2$, $c=0$, and $X_0=1$. Then $X_{n+1}=2X_n \pmod{10},$ and the sequence is...