#math-project
TAOCP 4.6.1 Exercise 19
Section 4.6.1: Division of Polynomials Exercise 19. [ M39 ] (Common divisors of square matrices.) Exercise 18 shows that the concept of greatest common right divisor can be meaningful when multiplication is not commutative. Prove that any two $n \times n$ matrices $A$ and $B$ of integers have a greatest common right matrix divisor $D$. [ Suggestion: Design an algorithm whose inputs are $A$ and $B$ and whose outputs are...
TAOCP 4.6.1 Exercise 20
Section 4.6.1: Division of Polynomials Exercise 20. [ M40 ] Investigate approximate polynomial gcds and the accuracy of Euclid's algorithm: What can be said about calculation of the greatest common divisor of polynomials whose coefficients are floating point numbers? Verified: no Solve time: 3m34s Setup The exercise asks for an investigation rather than a theorem with a single conclusion. Let $u(x),v(x)\in \mathbf{R}[x]$ have coefficients represented in floating-point arithmetic. We seek...
TAOCP 4.5.4 Exercise 45
Section 4.5.4: Factoring into Primes Exercise 45. ▶ [ M41 ] (J. M. Pollard and Claus-Peter Schnorr.) Find an efficient algorithm to solve the congruence $$x^2 - ay^2 \equiv b \pmod{n}$$ for integers $x$ and $y$, given integers $a$, $b$, and $n$ with $ab \perp n$ and $n$ odd, even if the factorization of $n$ is unknown. [ Hint: Use the identity $(x_1^2 - ay_1^2)(x_2^2 - ay_2^2) = x^2 -...
TAOCP 4.5.4 Exercise 40
Section 4.5.4: Factoring into Primes Exercise 40. ▶ [ M36 ] (A. Shamir.) Consider an abstract computer that can perform the operations $x + y$, $x - y$, $x \cdot y$, and $\lfloor x/y \rfloor$ on integers $x$ and $y$ of arbitrary length, in just one unit of time, no matter how large those integers are. The machine stores integers in a random-access memory and it can select different program...
TAOCP 4.5.3 Exercise 41
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 41. [ M40 ] (J. Shallit, 1979.) Show that the regular continued expansion of $$\frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^4} + \cdots = \sum_{n \ge 0} \frac{1}{2^{2^n}}$$ contains only 1s and 2s and has a fairly simple pattern. Prove that the partial quotients of Liouville's numbers $\sum_{n \ge 1} l^{-n!}$ also have a regular pattern, when $l$ is any integer $\ge 2$. [The latter...
TAOCP 4.5.3 Exercise 37
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 37. [ M38 ] (T. S. Motzkin and E. G. Straus.) Let $a_1, \ldots, a_n$ be positive integers. Show that $\max K_s(a_{p(1)}, \ldots, a_{p(n)})$, over all permutations $p(1) \ldots p(n)$ of ${1, 2, \ldots, n}$, occurs when $a_{p(1)} \ge a_{p(n)} \ge a_{p(2)} \ge a_{p(n-1)} \ge \cdots$; and the minimum occurs when $a_{p(1)} \le a_{p(n)} \le a_{p(2)} \le a_{p(n-1)} \le \cdots \le a_{p(4)} \le...
TAOCP 4.5.3 Exercise 13
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 13. [ M40 ] (J. Lagrange, 1767.) Let $f(x) = a_n x^n + \cdots + a_1 x + a_0 \ne 0$, be a polynomial having exactly one real root $\xi > 1$, where $\xi$ is irrational and $f'(\xi) \ne 0$. Experiment with a computer program to find the first thousand or so partial quotients of $\xi$, using the following algorithm (which essentially involves...
TAOCP 4.4 Exercise 17
Section 4.4: Radix Conversion Exercise 17. [ M40 ] Design "ideal" floating point conversion subroutines, taking $p$-digit decimal numbers into $P$-digit binary numbers and vice versa, in both cases producing a true rounded result in the sense of Section 4.2.2. Verified: no Solve time: 8m01s Solution Let $$ \mathcal D(p)={\pm (0.d_1d_2\cdots d_p)_{10},10^e : d_1\neq0} $$ be the set of normalized $p$-digit decimal floating-point numbers, and let $$ \mathcal B(P)={\pm (0.b_1b_2\cdots...
TAOCP 4.3.3 Exercise 12
Section 4.3.3: How Fast Can We Multiply? Exercise 12. ▶ [ M41 ] (A. Schönhage.) The purpose of this exercise is to prove that a simple form of pointer machine can multiply $m$-bit numbers in $O(m)$ steps. The machine has no built-in facilities for arithmetic; all it does is work with nodes and pointers. Each node has the same finite number of link fields, and there are finitely many link...
TAOCP 4.2.2 Exercise 18
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 18. [ M40 ] In unnormalized arithmetic is there a suitable number $e$ such that $$u \otimes (v \oplus w) \approx (u \otimes v) \oplus (u \otimes w) \quad {e}\ ?$$ Verified: yes Solve time: 2m11s Setup In unnormalized arithmetic, floating point addition and multiplication are still defined by u\otimes v=\operatorname{round}(uv),$$ but numbers need not be normalized. Let the radix be $b$...
TAOCP 4.1 Exercise 33
Section 4.1: Positional Number Systems Exercise 33. [ M40 ] (D. A. Klarner.) Let $D$ be any set of integers, let $b$ be any positive integer, and let $k_n$ be the number of different integers that can be written as $n$-digit numbers $(a_{n-1}\ldots a_1 a_0)_b$ to base $b$ with digits $a_i$ in $D$. Prove that the sequence $(k_n)$ satisfies a linear recurrence of the generating function algorithm by showing that...
TAOCP 4.1 Exercise 32
Section 4.1: Positional Number Systems Exercise 32. [ M40 ] (I. Z. Ruzsa.) Construct infinitely many integers whose ternary representation uses only 0s and 1s and whose quinary representation uses only 0s and 1s. Verified: yes Solve time: 5m45s Setup Let $$ A=\left{\sum_{i=0}^{m} a_i3^i ;:; a_i\in{0,1},\ m\ge0\right} $$ be the set of nonnegative integers whose ternary representation uses only the digits $0$ and $1$. Let $$ B=\left{\sum_{j=0}^{n} b_j5^j ;:; b_j\in{0,1},\...
TAOCP 3.5 Exercise 37
Section 3.5: What Is a Random Sequence? Exercise 37. [ M37 ] (D. Coppersmith.) Define a sequence that satisfies Definition R4 but not Definition R5. [ Hint: Consider changing $U_0, U_1, U_4, U_9, \ldots$ in a truly random sequence.] Verified: yes Solve time: 1m15s Setup We are asked to construct a sequence that satisfies Definition R4 but fails Definition R5 . Let us first recall the relevant definitions from Section...
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 2.3.2 Exercise 17
Section 2.3.2: Binary Tree Representation of Trees Exercise 17. [ M40 ] Write a program to do algebraic simplification capable of reducing, for example, (20) or (21) to (22) . [ Hints: Include a new field with each node, representing its coefficient (for summands) or its exponent (for factors in a product). Apply algebraic identities, like replacing \ln(u ↑ v) by v \ln u ; remove the operations - ,...
TAOCP 2.2.1 Exercise 11
Section 2.2.1: Stacks, Queues, and Deques Exercise 11. [ M40 ] As a consequence of exercises 9 and 10, the number $b_n$ is the number of admissible sequences of length $2n$. Find a closed form for the generating function $\sum_{n \ge 0} b_n z^n$. Verified: yes Solve time: 1m12s Setup Let $b_n$ denote the number of permutations of $1,2,\ldots,n$ obtainable with an input-restricted deque. By Exercise 9, $b_n$ is also...
TAOCP 1.3.3 Exercise 24
Section 1.3.3: Applications to Permutations Exercise 24. [ M41 ] Find the variance of the quantity $A$ that enters into the timing of Algorithm $J$. (See exercise 14.) Verified: yes Solve time: 4m38s Let the permutation be decomposed into cycles, and let $\alpha_k$ denote the number of cycles of length $k$. In the timing analysis of Algorithm $J$ from Exercise 14, the quantity $A$ is the total number of repetitions...
TAOCP 1.2.9 Exercise 26
Section 1.2.9: Generating Functions Exercise 26. [ M40 ] Explore a generalization of the notation (31) according to which we might write, for example, $[z^2 - 2z^5]G(z)=a_2-2a_5$ when $G(z)$ is given by (1). Verified: yes Solve time: 42s Setup Let $$ G(z)=\sum_{n\ge 0} a_n z^n. $$ For each nonnegative integer $k$, the coefficient extraction operator satisfies $$ [z^k]G(z)=a_k. $$ Let $P(z)=\sum_{k=0}^m c_k z^k$ be a polynomial. The expression to be...
TAOCP 1.2.8 Exercise 30
Section 1.2.8: Fibonacci Numbers Exercise 30. [ M38 ] (D. Jarden, T. Motzkin.) The sequence of $m$th powers of Fibonacci numbers satisfies a recurrence relation in which each term depends on the preceding $m+1$ terms. Show that $$ \sum_k \binom{m}{k} {\mathcal{F}} (-1)^{\lceil (m-k)/2 \rceil} F {n+k}^{,m-1} = 0, \qquad \text{if } m>0. $$ For example, when $m=3$ we get the identity $F_n^2 - 2F_{n+1}^2 - 2F_{n+2}^2 + F_{n+3}^2 = 0$....