#simple
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 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.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.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 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 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 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 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 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 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 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...
TAOCP 2.3.3 Exercise 7
Section 2.3.3: Other Representations of Trees Exercise 7. [ 15 ] What classes would appear in (12) if the relation 9 ≡ 3 had not been given in (11) ? Verified: yes Solve time: 1m18s Solution The relation $9 \equiv 3$ serves only to place the element $9$ into the equivalence class containing $3$. If this relation is omitted from the list of relations in $(11)$, no chain of equivalences...
TAOCP 2.3.3 Exercise 8
Section 2.3.3: Other Representations of Trees Exercise 8. [ 15 ] Algorithm E sets up a tree structure that represents the given pairs of equivalent elements, but the text does not mention explicitly how the result of Algorithm E can be used. Design an algorithm that answers the question, " Is j ≡ k? ", assuming that 1 <= j <= n , 1 <= k <= n , and...
TAOCP 2.3.1 Exercise 15
Section 2.3.1: Traversing Binary Trees Exercise 15. [ 15 ] In a threaded-tree representation like (10) , each node except the list head has exactly one link pointing to it from above, namely the link from its parent. Some of the nodes also have links pointing to them from below; for example, the node containing C has two pointers coming up from below, while node E has just one. Is...
TAOCP 2.3.1 Exercise 2
Section 2.3.1: Traversing Binary Trees Exercise 2. [ 11 ] List the nodes of the binary tree in (a) preorder; (b) symmetric order; (c) postorder. Verified: no Solve time: 38s Solution Let T denote the root of the binary tree in the figure. We denote the left and right links of a node P by LLINK(P) and RLINK(P) , and the value of the node by INFO(P) . Traversals are...
TAOCP 2.3.1 Exercise 1
Section 2.3.1: Traversing Binary Trees Exercise 1. [ 01 ] In the binary tree (2) , let INFO(P) denote the letter stored in NODE(P) . What is INFO(LLINK(RLINK(RLINK(T)))) ? Verified: no Solve time: 30s In tree (2), the root is $A$, so $RLINK(T)$ points to $C$. The right child of $C$ is $F$, hence $RLINK(RLINK(T))$ points to $F$. The left child of $F$ is $H$, so $$ LLINK(RLINK(RLINK(T))) $$ points...
TAOCP 2.3.2 Exercise 11
Section 2.3.2: Binary Tree Representation of Trees Exercise 11. [ 15 ] Draw trees analogous to those shown in (7) , corresponding to the formula $$ y = e^{-x^2}. $$ Verified: yes Solve time: 2m12s Solution We are asked to draw trees analogous to those in (7) corresponding to the formula $$ y = e^{-x^2}. $$ Following the conventions in Section 2.3.2, we first construct the rooted formula tree ....
TAOCP 2.2.4 Exercise 7
Section 2.2.4: Circular Lists Exercise 7. [ 10 ] Why is it useful to assume that the ABC fields of a polynomial list appear in decreasing order? Verified: yes Solve time: 44s The decreasing order of the ABC fields makes it possible to combine two polynomials efficiently by a single systematic scan through their lists. In Algorithm A , the terms of polynomial(P) and polynomial(Q) are compared in step A2...
TAOCP 2.2.3 Exercise 1
Section 2.2.3: Linked Allocation Exercise 1. [ 10 ] Operation (9) for popping up a stack mentions the possibility of UNDERFLOW ; why doesn't operation (8), pushing down a stack, mention the possibility of OVERFLOW ? Verified: no Solve time: 39s Operation (8) does not mention OVERFLOW because it assumes that a new node can always be obtained from the AVAIL stack or the storage pool. In the formulation of...
TAOCP 2.2.4 Exercise 8
Section 2.2.4: Circular Lists Exercise 8. [ 10 ] Why is it useful to have Q1 trailing one step behind Q in Algorithm A ? Verified: yes Solve time: 45s The pointer Q1 trails Q by one node to simplify insertions and deletions in polynomial(Q) . In step A4 , when a term of Q becomes zero and must be removed, the assignment LINK(Q1) \leftarrow Q \leftarrow LINK(Q) relies on...
TAOCP 2.2.1 Exercise 2
Section 2.2.1: Stacks, Queues, and Deques Exercise 2. [ 15 ] Imagine four railroad cars positioned on the input side of the track in Fig. 1, numbered $1$, $2$, $3$, and $4$, from left to right. Suppose we perform the following sequence of operations (which is compatible with the direction of the arrows in the diagram and does not require cars to "jump over" other cars): (i) move car $1$...
TAOCP 2.2.2 Exercise 6
Section 2.2.2: Sequential Allocation Exercise 6. [ 10 ] Starting with the memory configuration shown in Fig. 4, determine which of the following sequences of operations causes overflow or underflow: $(a)\ I_1;\quad (b)\ I_2;\quad (c)\ I_3;\quad (d)\ I_4I_4I_4I_4I_4;\quad (e)\ D_2D_2I_2I_2I_2.$ Verified: no Solve time: - Using the memory configuration of Fig. 4, stacks 1, 2, and 3 are empty, while stack 4 occupies the available space to the right. Hence...
TAOCP 1.4.4 Exercise 2
Section 1.4.4: Input and Output Exercise 2. [ 10 ] The instructions OUT 1000(6); JBUS *(6) may be used to output a tape block in an unbuffered fashion, just as the instructions (1) did this for input. Give a method analogous to (2) and (3) that buffers this output, by using MOVE instructions and an auxiliary buffer in locations 2000-2099. Verified: yes Solve time: 44s The output tape is used...
TAOCP 1.4.4 Exercise 6
Section 1.4.4: Input and Output Exercise 6. [ 12 ] What instructions should be placed at the beginning of a program so that the WORDIN subroutine (4) gets off to the right start? (For example, index register 6 must be set to something .) Verified: no Solve time: - Solution To initialize the WORDIN subroutine (4) correctly, we must ensure that the first call to WORDIN will access the first...
TAOCP 2.2.2 Exercise 7
Section 2.2.2: Sequential Allocation Exercise 7. [ 12 ] Step G4 of Algorithm G indicates a division by the quantity INC . Can INC ever be zero at that point in the algorithm? Verified: no Solve time: - Solution Step G4 of Algorithm G sets $$ \alpha \leftarrow 0.1 \times \frac{\text{SUM}}{n},\qquad \beta \leftarrow 0.9 \times \frac{\text{SUM}}{\text{INC}}. $$ The quantity INC was computed in step G2 as $$ \text{INC} \leftarrow \sum_{j=1}^{n}...
TAOCP 2.2.2 Exercise 1
Section 2.2.2: Sequential Allocation Exercise 1. [ 15 ] In the queue operations given by (6a) and (7a), how many items can be in the queue at one time without OVERFLOW occurring? Verified: no Solve time: - Solution Let $X[1], \ldots, X[M]$ be the memory locations for the queue, with F and R the front and rear pointers, respectively, as in (6a) and (7a). The queue is initially empty when...
TAOCP 1.4.4 Exercise 1
Section 1.4.4: Input and Output Exercise 1. [ 05 ] (a) Would sequence (3) still be correct if the MOVE instructions were placed before the JBUS instruction instead of after it? (b) What if the MOVE instructions were placed after the IN command? Verified: no Solve time: - (a) Yes. If the two MOVE instructions are executed before JBUS *(5) , they merely copy the contents of locations 2000-2099 into...
TAOCP 1.4.4 Exercise 8
Section 1.4.4: Input and Output Exercise 8. [ 11 ] The text describes a hypothetical input scenario that leads from Fig. 23 through parts (a), (b), and (c) of Fig. 24. Interpret the same scenario under the assumption that output to the line printer is being done, instead of input from cards. (For example, what things are happening at the time shown in Fig. 23?) Verified: yes Solve time: 47s...
TAOCP 2.2.1 Exercise 1
Section 2.2.1: Stacks, Queues, and Deques Exercise 1. [ 06 ] An input-restricted deque is a linear list in which items may be inserted at one end but removed from either end; clearly an input-restricted deque can operate either as a stack or as a queue, if we consistently remove all items from one of the two ends. Can an output-restricted deque also be operated either as a stack or...
TAOCP 1.4.3.1 Exercise 4
Section 1.4.3.1: A MIX Simulator Exercise 4. [ 14 ] Change the program in the text so that it begins as though MIX's "GO button" had been pushed (see exercise 1.3.1-26 ). Verified: yes Solve time: 39s Solution Exercise 1.4.3.1.4 [ 14 ] asks to modify the MIX simulator program so that it begins execution as though MIX's "GO button" had been pushed. In the MIX hardware, pushing the GO...
TAOCP 1.4.3.1 Exercise 1
Section 1.4.3.1: A MIX Simulator Exercise 1. [ 14 ] Study all the uses of the FCHECK subroutine in the simulator program. Can you suggest a better way to organize the code? (See step 3 in the discussion at the end of Section 1.4.1 .) Verified: yes Solve time: 1m20s Solution The subroutine FCHECK is called whenever an instruction uses a field specification. The sequence JMP FCHECK appears inside GETV...
TAOCP 1.4.3.2 Exercise 3
Section 1.4.3.2: Trace Routines Exercise 3. [ 10 ] The previous exercise suggests having the trace program write its output onto tape. Discuss why this would be preferable to printing directly. Verified: no Solve time: - Writing trace output onto tape rather than printing directly is preferable because tape allows information to be recorded sequentially without interrupting the execution of the program being traced. Direct printing would require the program...
TAOCP 1.3.3 Exercise 11
Section 1.3.3: Applications to Permutations Exercise 11. [ 15 ] Find a simple rule for writing $\pi^{-}$ in cycle form, if the permutation $\pi$ is given in cycle form. Verified: yes Solve time: 1m28s Solution Let $\pi$ be a permutation expressed in cycle form as a product of disjoint cycles: $$ \pi = (x_{11} x_{12} \dots x_{1n_1})(x_{21} x_{22} \dots x_{2n_2})\cdots(x_{k1} x_{k2} \dots x_{kn_k}), $$ where each cycle $(x_{i1} x_{i2} \dots...
TAOCP 1.3.1 Exercise 6
Section 1.3.1: Description of MIX Exercise 6. [ 10 ] Assume that location 3000 contains + 5 1 200 15 What is the result of the following instructions? (State if any of them are undefined or only partially defined.) (a) LDAN 3000 ; (b) LD2N 3000(3:4) ; (c) LDX 3000(1:3) ; (d) LD6 3000 ; (e) LDXN 3000(0:0) . Verified: yes Solve time: 2m53s Solution to Exercise 1.3.1.6 [10] We...
TAOCP 1.3.1 Exercise 3
Section 1.3.1: Description of MIX Exercise 3. [ 02 ] Give the partial field specifications, (L:R) , for the (a) address field, (b) index field, (c) field field, and (d) operation code field of a MIX instruction. Verified: yes Solve time: 44s The instruction format of a MIX word places the sign in position $0$, the address in bytes $1$–$2$, the index specification in byte $3$, the field specification in...
TAOCP 1.3.1 Exercise 9
Section 1.3.1: Description of MIX Exercise 9. [ 15 ] List all the MIX operators that can possibly affect the setting of the overflow toggle. (Do not include floating point operators.) Verified: no Solve time: 4m04s Lời giải Bài toán yêu cầu liệt kê mọi toán tử MIX có thể ảnh hưởng đến overflow toggle , tức là những lệnh có thể đặt (set) hoặc xóa (clear) overflow toggle theo...
TAOCP 1.3.1 Exercise 11
Section 1.3.1: Description of MIX Exercise 11. [ 15 ] List all the MIX operators that can possibly affect the setting of rI1 . Verified: yes Solve time: 3m05s Solution The exercise asks for all MIX operators that can affect the setting of the index register $rI1$. To answer such a question, one must inspect the complete list of operators in §1.3.1 and determine which of them can alter the...
TAOCP 1.3.3 Exercise 2
Section 1.3.3: Applications to Permutations Exercise 2. [ 10 ] The text shows how we might set $(a, b, c, d, e, f) \leftarrow (c, d, f, b, e, a)$ by using a series of replacement operations $(x \leftarrow y)$ and one auxiliary variable $t$. Show how to do the job by using a series of exchange operations $(x \leftrightarrow y)$ and no auxiliary variables. Verified: yes Solve time: 1m22s...
TAOCP 1.3.3 Exercise 9
Section 1.3.3: Applications to Permutations Exercise 9. [ 10 ] Both Programs $A$ and $B$ accept the same input and give the answer in essentially the same form. Is the output exactly the same under both programs? Verified: yes Solve time: 1m04s No. The two programs do not necessarily produce exactly the same output. Program $A$ implements Algorithm $A$, which constructs the answer by choosing the first untagged element encountered...
TAOCP 1.3.1 Exercise 15
Section 1.3.1: Description of MIX Exercise 15. [ 10 ] How many alphanumeric characters are there in a typewriter or paper-tape block? in a card-reader or card-punch block? in a line-printer block? Verified: yes Solve time: 36s In MIX, each alphanumeric character is represented by one byte, since a byte holds at least $64$ distinct values and is used for character coding in input-output operations. Thus the number of characters...
TAOCP 1.3.2 Exercise 5
Section 1.3.2: The MIX Assembly Language Exercise 5. [ 11 ] Why doesn't Program P need a JBUS instruction to determine when the line printer is ready? Verified: yes Solve time: 1m23s Solution Program P uses the output instruction OUT buffer(PRINTER) on lines 25 and 35, but nowhere uses JBUS *(PRINTER) to test whether the printer is available. The reason is that the algorithm employs two buffers, BUF0 and BUF1...
TAOCP 1.3.3 Exercise 1
Section 1.3.3: Applications to Permutations Exercise 1. [ 02 ] Consider the transformation of ${0, 1, 2, 3, 4, 5, 6}$ that replaces $x$ by $2x \bmod 7$. Show that this transformation is a permutation, and write it in cycle form. Verified: yes Solve time: 1m07s Let $f(x)=2x \bmod 7$ on ${0,1,2,3,4,5,6}$. Since $\gcd(2,7)=1$, there exists $2^{-1}\equiv 4 \pmod 7$, so $x\mapsto 2x \bmod 7$ is invertible with inverse $x\mapsto...
TAOCP 1.3.3 Exercise 4
Section 1.3.3: Applications to Permutations Exercise 4. [ 10 ] Express $(abd)(ef)(acf)(bd)$ as a product of disjoint cycles. Verified: yes Solve time: 2m50s Corrected Solution to Exercise 1.3.3.4 (4) We are asked to express $$ (abd)(ef)(acf)(bd) $$ as a product of disjoint cycles, using Knuth's left-to-right convention for composition of permutations. Step 1: Compute the image of each element 1. Image of $a$: $$ a \xrightarrow{(abd)} b \xrightarrow{(ef)} b \xrightarrow{(acf)}...
TAOCP 1.3.1 Exercise 5
Section 1.3.1: Description of MIX Exercise 5. [ 10 ] What symbolic notation, analogous to (4), corresponds to (6) if (6) is regarded as a MIX instruction? Verified: yes Solve time: 3m09s Let (6) be a MIX word written in its physical layout as $$ (6):\quad \pm ; \text{AA} ; \text{I} ; \text{F} ; \text{C}, $$ where AA is the address field, I the index field, F the field specification,...
TAOCP 1.3.3 Exercise 3
Section 1.3.3: Applications to Permutations Exercise 3. [ 03 ] Compute the product $$ \begin{pmatrix} a & b & c & d & e & f \ b & d & c & a & f & e \end{pmatrix} \times \begin{pmatrix} a & b & c & d & e & f \ c & d & f & b & e & a \end{pmatrix}, $$ and express the answer...
TAOCP 1.3.2 Exercise 7
Section 1.3.2: The MIX Assembly Language Exercise 7. [ 10 ] (a) What is the meaning of 4B in line 34 of Program P ? (b) What effect, if any, would be caused if the location of line 15 were changed to 2H and the address of line 20 were changed to 2B ? Verified: yes Solve time: 3m03s In MIX assembly (as used in The Art of Computer Programming...
TAOCP 1.3.1 Exercise 19
Section 1.3.1: Description of MIX Exercise 19. [ 14 ] What is the execution time of the program in the preceding exercise, not counting the HLT instruction? Verified: yes Solve time: 1m05s Solution The execution times given in Section 1.3.1 are: $$ \begin{aligned} &\text{all STORE operations} &&= 2,\ &\text{all shift operations} &&= 2,\ &\text{ADD} &&= 2,\ &\text{all comparison operations} &&= 2,\ &\text{MOVE of } n \text{ words} &&= 2n+1,\ &\text{NUM,...
TAOCP 1.3.1 Exercise 12
Section 1.3.1: Description of MIX Exercise 12. [ 10 ] Find a single instruction that has the effect of multiplying the current contents of rI3 by two and leaving the result in rI3 . Verified: yes Solve time: 5m27s Corrected solution The proposed solution fails because MMIX provides no arithmetic or shift instructions that operate directly on index registers $rI_0,\dots,rI_7$. These registers are not part of the general ALU register...
TAOCP 1.3.1 Exercise 13
Section 1.3.1: Description of MIX Exercise 13. [ 10 ] Suppose location 1000 contains the instruction JOV 1001 . This instruction turns off the overflow toggle if it is on (and the next instruction executed will be in location 1001, in any case). If this instruction were changed to JNOV 1001 , would there be any difference? What if it were changed to JOV 1000 or JNOV 1000 ? Verified:...
TAOCP 1.3.3 Exercise 7
Section 1.3.3: Applications to Permutations Exercise 7. [ 10 ] If Program $A$ is presented with the input (6), what are the quantities $X$, $Y$, $M$, $N$, $U$, and $V$ of (19)? What is the time required by Program $A$, excluding input-output? Verified: no Solve time: 4m51s Let $$ P=(acfg)(bcd)(aed)(fade)(bgfae), $$ with permutations composed from right to left. We first determine the quantities $X,Y,M,N,U,V$ of (19). The input contains $5$...
TAOCP 1.3.1 Exercise 2
Section 1.3.1: Description of MIX Exercise 2. [ 02 ] If a value to be represented within MIX may get as large as 99999999, how many adjacent bytes should be used to contain this quantity? Verified: yes Solve time: 35s Four adjacent bytes represent integers from $0$ through $16{,}777{,}215$ by the table in Section 1.3.1. Since $$ 99{,}999{,}999 > 16{,}777{,}215, $$ no representation using four adjacent bytes can accommodate all...
TAOCP 1.3.2 Exercise 2
Section 1.3.2: The MIX Assembly Language Exercise 2. ▶ [ 10 ] Line 12 of Program M says JMP * , where * denotes the location of that line. Why doesn't the program go into an infinite loop, endlessly repeating this instruction? * The author was astonished to learn in 1971 that MIXAL is also the name of a laundry detergent in Yugoslavia, developed for use with automate [automatics]. Verified:...
TAOCP 1.3.1 Exercise 10
Section 1.3.1: Description of MIX Exercise 10. [ 15 ] List all the MIX operators that can possibly affect the setting of the comparison indicator. Verified: yes Solve time: 51s Solution The comparison indicator $\mathrm{CI}$ takes one of the three values $\mathrm{LESS}$, $\mathrm{EQUAL}$, or $\mathrm{GREATER}$. From the instruction tables in Section 1.3.1, $\mathrm{CI}$ is assigned only by instructions of the comparison family. The relevant definition is given in the instruction...
TAOCP 1.3.1 Exercise 8
Section 1.3.1: Description of MIX Exercise 8. [ 15 ] The last example of the DIV instruction that appears on page 133 has " rX before " equal to + 1235 0 3 1 If this were - 1234 0 3 1 instead, but other parts of that example were unchanged, what would registers A and X contain after the DIV instruction? Table 1 Character code Code Char Code Char...
TAOCP 1.2.8 Exercise 10
Section 1.2.8: Fibonacci Numbers Exercise 10. [ 15 ] Is $\phi^n/\sqrt{5}$ greater than $F_n$ or less than $F_n$? Verified: no Solve time: - Solution From equation (14) we have the exact expression $$ F_n = \frac{1}{\sqrt{5}}\left(\phi^n - \hat{\phi}^n\right), $$ where $$ \hat{\phi} = 1 - \phi = -\frac{1}{\phi} = \frac{1}{2}(1 - \sqrt{5}). $$ Thus the difference between $\phi^n/\sqrt{5}$ and $F_n$ is $$ \frac{\phi^n}{\sqrt{5}} - F_n = \frac{\phi^n}{\sqrt{5}} - \frac{1}{\sqrt{5}}\left(\phi^n -...
TAOCP 1.2.8 Exercise 4
Section 1.2.8: Fibonacci Numbers Exercise 4. [ 14 ] Find all $n$ for which $F_n=n$. Verified: yes Solve time: 38s Solution By Eq. (14), $$ F_n=\frac{1}{\sqrt5}(\phi^n-\hat\phi^n), $$ where $$ \phi=\frac{1+\sqrt5}{2}, \qquad \hat\phi=\frac{1-\sqrt5}{2}. $$ The values $$ F_0=0,\qquad F_1=1,\qquad F_5=5 $$ show that $$ n=0,;1,;5 $$ are solutions of the equation $F_n=n$. It remains to prove that no other solutions exist. For $n\ge 6$, Section 1.2.1 gives $$ F_n\ge \phi^{,n-2}. $$...
TAOCP 1.2.7 Exercise 2
Section 1.2.7: Harmonic Numbers Exercise 2. [ 13 ] Show that the simple argument used in the text to prove that $H_{2^m} \ge 1 + m/2$ can be slightly modified to prove that $H_{2^m} \le 1 + m$. Verified: no Solve time: - Solution The argument in the text groups the terms of $H_{2^m}$ as follows: $$ H_{2^m} = 1 + \frac12 \left(\frac13 + \frac14\right) \left(\frac15 + \cdots + \frac18\right)...
TAOCP 1.2.7 Exercise 4
Section 1.2.7: Harmonic Numbers Exercise 4. [ 10 ] Decide which of the following statements are true for all positive integers $n$: $H_n < \ln n$. $H_n > \ln n$. $H_n > \ln n + \gamma$. Verified: no Solve time: - Statement 1 is false, since $H_1=1>\ln 1=0$. Statement 2 is true for all positive integers $n$. Since $1/x$ is decreasing on $[1,n]$, $$ \int_k^{k+1}\frac{dx}{x}<\frac{1}{k} \qquad (1\le k\le n-1). $$...
TAOCP 1.2.8 Exercise 7
Section 1.2.8: Fibonacci Numbers Exercise 7. [ 15 ] If $n$ is not a prime number, $F_n$ is not a prime number (with one exception). Prove this and find the exception. Verified: no Solve time: - Solution Assume that $n$ is composite. Then there exist integers $a,b$ such that $$ n=ab, \qquad a>1, \qquad b>1. $$ By the remark following Eq. (6), if $m$ is a multiple of $n$, then...
TAOCP 1.2.8 Exercise 8
Section 1.2.8: Fibonacci Numbers Exercise 8. [ 15 ] In many cases it is convenient to define $F_n$ for negative $n$, by assuming that $F_{n+2}=F_{n+1}+F_n$ for all integers $n$. Explore this possibility: What is $F_{-1}$? What is $F_{-2}$? Can $F_{-n}$ be expressed in a simple way in terms of $F_n$? Verified: no Solve time: - Solution We extend the Fibonacci sequence to negative indices by the recurrence $$ F_{n+2} =...
TAOCP 1.2.7 Exercise 1
Section 1.2.7: Harmonic Numbers Exercise 1. [ 01 ] What are $H_0$, $H_1$, and $H_2$? Verified: no Solve time: - By definition, $$ H_n = \sum_{k=1}^{n}\frac1k. $$ The empty sum gives $$ H_0 = 0. $$ Furthermore, $$ H_1 = 1, \qquad H_2 = 1+\frac12 = \frac32. $$ Therefore, $$ \boxed{H_0=0,\quad H_1=1,\quad H_2=\frac32.} $$
TAOCP 1.2.7 Exercise 5
Section 1.2.7: Harmonic Numbers Exercise 5. [ 15 ] Give the value of $H_{10000}$ to 15 decimal places, using the tables in Appendix A. Verified: no Solve time: - Solution By the asymptotic expansion for harmonic numbers in Appendix A, $$ H_n = \ln n + \gamma + \frac{1}{2n} -\frac{1}{12n^2} +\frac{1}{120n^4} -\frac{1}{252n^6} +\cdots . $$ For $n=10000$, $$ \ln 10000 = 4\ln 10. $$ Using the tables in Appendix A,...
TAOCP 1.2.8 Exercise 1
Section 1.2.8: Fibonacci Numbers Exercise 1. [ 10 ] What is the answer to Leonardo Fibonacci's original problem: How many pairs of rabbits are present after a year? Verified: no Solve time: - Fibonacci's original problem assumes that a pair of rabbits produces a new pair every month, starting from one newly born pair, and that rabbits become productive after one month. Let $F_n$ denote the number of pairs at...
TAOCP 1.2.6 Exercise 7
Section 1.2.6: Binomial Coefficients Exercise 7. [ 12 ] If $n$ is a fixed positive integer, what value of $k$ makes $\binom{n}{k}$ a maximum? Verified: yes Solve time: 37s Solution By Eq. (5), $$ \binom{n}{k}=\frac{n!}{k!(n-k)!}, \qquad 0\le k\le n. $$ To determine where this quantity is maximal, compare consecutive terms. For $0\le k<n$, $$ \frac{\binom{n}{k+1}}{\binom{n}{k}} = \frac{n!}{(k+1)!(n-k-1)!} \frac{k!(n-k)!}{n!} = \frac{n-k}{k+1}. $$ Hence $$ \binom{n}{k+1}>\binom{n}{k} \iff \frac{n-k}{k+1}>1 \iff n-k>k+1 \iff n>2k+1,...
TAOCP 1.2.6 Exercise 9
Section 1.2.6: Binomial Coefficients Exercise 9. [ 01 ] What is the value of $\binom{n}{n}$? (Consider all integers $n$.) Verified: yes Solve time: 39s For every integer $n \ge 0$, Eq. (5) gives $$ \binom{n}{n} = \frac{n!}{n!(n-n)!} = \frac{n!}{n!,0!}. $$ Since $\binom{r}{0}=1$ by Eq. (4), Eq. (5) with $n=0$ implies $0!=1$; hence $$ \binom{n}{n}=1. $$ If $n<0$, Eq. (3) defines $\binom{r}{k}=0$ whenever the lower argument $k$ is a negative integer....
TAOCP 1.2.6 Exercise 6
Section 1.2.6: Binomial Coefficients Exercise 6. [ 10 ] Pascal's triangle (Table 1) can be extended in all directions by use of the addition formula, Eq. (9). Find the three rows that go on top of Table 1 (i.e., for $r=-1$, $-2$, and $-3$). Verified: yes Solve time: 41s Using Eq. (9), $$ \binom{r}{k}=\binom{r-1}{k}+\binom{r-1}{k-1}, $$ the rows above Table 1 are determined uniquely by working upward. Since every entry equals...
TAOCP 1.2.6 Exercise 4
Section 1.2.6: Binomial Coefficients Exercise 4. [ 10 ] Give the answer to exercise 3 as a product of prime numbers. Verified: no Solve time: 29s By Exercise 3, the number of bridge hands is $$ \binom{52}{13} = \frac{52!}{13!,39!} = \frac{52\cdot51\cdot50\cdots40}{13!}. $$ Factoring each term into primes and canceling the factors of $13!$, we obtain $$ \binom{52}{13} = 2^2\cdot3^3\cdot5\cdot7\cdot11\cdot17\cdot19\cdot23\cdot41\cdot43\cdot47. $$ Hence the number of bridge hands, expressed as a product...
TAOCP 1.2.6 Exercise 5
Section 1.2.6: Binomial Coefficients Exercise 5. [ 05 ] Use Pascal's triangle to explain the fact that $11^4 = 14641$. Verified: yes Solve time: 41s The rows of Pascal's triangle give the coefficients of the expansion of $(x+y)^n$ according to the binomial theorem, Eq. (13). The fourth row (corresponding to $n=4$) is $1, 4, 6, 4, 1$. Substituting $x = 10$ and $y = 1$, we have = \binom{4}{0}10^0 +...
TAOCP 1.2.3 Exercise 23
Section 1.2.3: Sums and Products Exercise 23. [ 10 ] Explain why it is a good idea to define $\sum_{R(j)} a_j$ and $\prod_{R(j)} a_j$ as zero and one, respectively, when no integers satisfy $R(j)$. Verified: yes Solve time: 39s Defining $\sum_{R(j)} a_j = 0$ when no integers satisfy $R(j)$ preserves the additive identity. That is, if we consider an arbitrary sum $\sum_{R(j)} a_j + \sum_{S(j)} a_j$ and some value of...
TAOCP 1.2.4 Exercise 10
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 10. ▶ [ 10 ] What are $1.1 \bmod 1$, $0.11 \bmod 0.1$, $0.11 \bmod (-0.1)$? Verified: yes Solve time: 1m10s By equation (1), $$ x \bmod y = x - y\left\lfloor \frac{x}{y}\right\rfloor. $$ For $1.1 \bmod 1$, $$ 1.1 \bmod 1 =1.1-\left\lfloor 1.1\right\rfloor =1.1-1 =0.1. $$ For $0.11 \bmod 0.1$, $$ 0.11 \bmod 0.1 =0.11-0.1\left\lfloor \frac{0.11}{0.1}\right\rfloor =0.11-0.1\lfloor 1.1\rfloor =0.11-0.1 =0.01....
TAOCP 1.2.4 Exercise 14
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 14. ▶ [ 12 ] If $x \bmod 3 = 2$ and $x \bmod 5 = 3$, what is $x \bmod 15$? Verified: yes Solve time: 34s Solution Let $x \equiv 2 \pmod 3,$ $x \equiv 3 \pmod 5.$ Since $3 \perp 5$, Law D implies that these two congruences determine a unique congruence class modulo $15$. Write $x=3k+2.$ Substituting into...
TAOCP 1.2.4 Exercise 9
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 9. [ 05 ] What are $5 \bmod (-3)$, $18 \bmod (-3)$, $-2 \bmod (-3)$? Verified: yes Solve time: 2m13s By equation (1), $$ x \bmod y = x-y\left\lfloor \frac{x}{y}\right\rfloor. $$ Hence $$ 5 \bmod (-3)=5-(-3)\left\lfloor \frac{5}{-3}\right\rfloor =5+3\lfloor -5/3\rfloor. $$ Since $\lfloor -5/3\rfloor=-2$, $$ 5 \bmod (-3)=5+3(-2)=-1. $$ Similarly, $$ 18 \bmod (-3)=18-(-3)\left\lfloor \frac{18}{-3}\right\rfloor =18+3(-6)=0, $$ and $$ -2 \bmod (-3)...
TAOCP 1.2.4 Exercise 15
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 15. [ 10 ] Prove that $z(x \bmod y) = (zx) \bmod (zy)$. [Law C is an immediate consequence of this distributive law.] Verified: yes Solve time: 1m03s By definition (1), $$ x \bmod y = x-y\left\lfloor \frac{x}{y}\right\rfloor . $$ Hence $$ z(x\bmod y) = z\left(x-y\left\lfloor \frac{x}{y}\right\rfloor \right) = zx-zy\left\lfloor \frac{x}{y}\right\rfloor . $$ Also, $$ \left\lfloor \frac{zx}{zy}\right\rfloor = \left\lfloor \frac{x}{y}\right\rfloor ,...
TAOCP 1.2.4 Exercise 2
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 2. ▶ [ 01 ] What is $\lceil \lfloor x \rfloor \rceil$? Verified: yes Solve time: 27s For any real number $x$, the floor function $\lfloor x \rfloor$ is an integer by definition. Applying the ceiling function to an integer does not change its value, since the ceiling of an integer is the integer itself. Therefore, we have $\lceil \lfloor x...
TAOCP 1.2.3 Exercise 25
Section 1.2.3: Sums and Products Exercise 25. ▶ [ 15 ] Consider the following derivation; is anything amiss? $$\left( \sum_{i=1}^n a_i \right) \left( \sum_{j=1}^n \frac{1}{a_j} \right) = \sum_{1 \le i \le n} \sum_{1 \le j \le n} \frac{a_i}{a_j} = \sum_{1 \le i \le n} \sum_{1 \le i \le n} \frac{a_i}{a_i} = \sum_{i=1}^n 1 = n.$$ Verified: yes Solve time: 59s Solution We are asked to examine the derivation $\left( \sum_{i=1}^n...
TAOCP 1.2.2 Exercise 5
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 5. [ 05 ] We defined real numbers in terms of a decimal expansion. Discuss how we could have defined them in terms of a binary expansion instead, and give a definition to replace Eq. (2). Verified: yes Solve time: 38s We could define real numbers by binary expansions instead of decimal expansions. In place of Eq. (1), every real number would be...
TAOCP 1.2.2 Exercise 3
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 3. [ 02 ] What is $(-3)^{-3}$? Verified: yes Solve time: 31s By Eq. (4), $(-3)^{-3} = \frac{(-3)^{-2}}{-3} = \frac{(-3)^{-1}}{(-3)^2} = \frac{1}{(-3)^3}.$ Since $(-3)^3 = (-3)(-3)(-3) = 9(-3) = -27,$ we obtain $(-3)^{-3} = \frac{1}{-27} = -\frac{1}{27}.$ Therefore the answer is $\boxed{-\frac{1}{27}}.$
TAOCP 1.2.3 Exercise 13
Section 1.2.3: Sums and Products Exercise 13. [ 10 ] Using Eq. (15) and assuming that $m \le n$, evaluate $\sum_{j=m}^n j$. Verified: yes Solve time: 37s We begin by expressing the sum in a form suitable for applying Eq. (15): $\sum_{j=m}^n j = \sum_{0 \le j \le n} j - \sum_{0 \le j \le m-1} j. \eqno(1)$ By Eq. (15), we have $\sum_{0 \le j \le n} j =...
TAOCP 1.2.3 Exercise 3
Section 1.2.3: Sums and Products Exercise 3. ▶ [ 13 ] Without using the $\sum$-notation, write out the equivalent of $$\sum_{0 \le n \le 5} \frac{1}{2n + 1},$$ and also the equivalent of $$\sum_{0 \le n^2 \le 5} \frac{1}{2n^2 + 1}.$$ Explain why the two results are different, in spite of rule (b). Verified: yes Solve time: 44s Solution The first sum is $\sum_{0 \le n \le 5} \frac{1}{2n+1}.$ The...
TAOCP 1.2.3 Exercise 9
Section 1.2.3: Sums and Products Exercise 9. ▶ [ 05 ] Is the derivation of Eq. (14) valid even if $n = -1$? Verified: yes Solve time: 1m04s Yes. The derivation remains valid when $n=-1$. For $n=-1$, the sum in Eq. (14) is $$ \sum_{0\le j\le -1} ax^j, $$ which is an empty sum and therefore has value $0$. Examine the derivation step by step. The relation $$ \sum_{0\le j\le...
TAOCP 1.2.2 Exercise 12
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 12. [ 02 ] Explain why Eq. (10) follows from Eqs. (8). Verified: yes Solve time: 36s Equation (8) shows that $$ 10^{0.30102999}=1.99999999739\ldots $$ and $$ 10^{0.30103000}=2.0000000199\ldots . $$ Since $$ 1.99999999739\ldots < 2 < 2.0000000199\ldots, $$ the number $2$ lies strictly between the values of $10^x$ corresponding to the decimal approximations $x=0.30102999$ and $x=0.30103000$. By the definition of logarithm, Eq. (9), the...
TAOCP 1.2.3 Exercise 4
Section 1.2.3: Sums and Products Exercise 4. [ 10 ] Without using the $\sum$-notation, write out the equivalent of each side of Eq. (10) as a sum of sums for the case $n = 3$. Verified: yes Solve time: 45s For $n = 3$, the left-hand side of Eq. (10) is $$ \sum_{i=1}^3 \sum_{j=1}^i a_{ij} = (a_{11}) + (a_{21} + a_{22}) + (a_{31} + a_{32} + a_{33}). $$ The right-hand...
TAOCP 1.2.3 Exercise 12
Section 1.2.3: Sums and Products Exercise 12. [ 10 ] What is $1 + \frac{1}{7} + \frac{1}{49} + \frac{1}{343} + \cdots + \left(\frac{1}{7}\right)^n$? Verified: yes Solve time: 36s The given sum is a finite geometric progression with first term $a = 1$, common ratio $x = \frac{1}{7}$, and $n+1$ terms. By equation (14), the sum of a geometric progression is $\sum_{0 \le j \le n} a x^j = a \frac{1...
TAOCP 1.2.2 Exercise 21
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 21. [ 15 ] ( Logs of logs .) Express $\log_b \log_b x$ in terms of $\ln \ln x$, $\ln \ln b$, and $\ln b$. Verified: yes Solve time: 29s Solution By equation (14), $$ \log_b y = \frac{\ln y}{\ln b}. $$ Set $y = \log_b x$. Then $$ \log_b \log_b x = \frac{\ln(\log_b x)}{\ln b}. $$ Applying equation (14) again to $\log_b...
TAOCP 1.2.2 Exercise 24
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 24. [ 15 ] Explain how the method used for calculating logarithms to the base 10 at the end of this section can be modified to produce logarithms to base 2. Verified: yes Solve time: 37s Solution The method based on Eqs. (17)–(19) computes $\log_{10} x$ by repeatedly squaring and comparing with the base $10$. To compute logarithms to base $2$, we replace...
TAOCP 1.2.2 Exercise 20
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 20. [ 10 ] Is there any simple relation between $\log_{10} 2$ and $\log_2 10$? Verified: yes Solve time: 36s Yes. By the change-of-base formula (14), $$ \log_2 10=\frac{\log_{10}10}{\log_{10}2}. $$ Since $\log_{10}10=1$, this becomes $$ \log_2 10=\frac{1}{\log_{10}2}. $$ Therefore the two quantities are reciprocals: $$ (\log_{10}2)(\log_2 10)=1. $$ Using Eq. (10), $$ \log_{10}2=0.30102999\ldots, $$ hence $$ \log_2 10=\frac{1}{0.30102999\ldots}=3.32192809\ldots. $$ Thus $$ \boxed{\log_2 10=\frac{1}{\log_{10}2}}....
TAOCP 1.2.3 Exercise 2
Section 1.2.3: Sums and Products Exercise 2. [ 01 ] What does the notation $\sum_{1 \le j \le n} a_j$ mean, if $n = 3.14$? Verified: yes Solve time: 1m01s By definition (2), $\sum_{1 \le j \le n} a_j$ denotes the sum of all terms $a_j$ for integer values of $j$ satisfying the condition $1 \le j \le n$. If $n=3.14$, the integers satisfying $1 \le j \le 3.14$ are...
TAOCP 1.2.3 Exercise 14
Section 1.2.3: Sums and Products Exercise 14. [ 11 ] Using the result of the previous exercise, evaluate $\sum_{j=m}^n \sum_{k=r}^s jk$. Verified: yes Solve time: 32s Solution By the distributive law (4), $$ \sum_{j=m}^n \sum_{k=r}^s jk = \left(\sum_{j=m}^n j\right)\left(\sum_{k=r}^s k\right). $$ Exercise 13 gives the evaluation $$ \sum_{j=m}^n j = \frac{1}{2}\bigl(n(n+1)-m(m-1)\bigr), $$ and similarly, $$ \sum_{k=r}^s k = \frac{1}{2}\bigl(s(s+1)-r(r-1)\bigr). $$ Substituting these values into the product yields $$ \sum_{j=m}^n \sum_{k=r}^s...
TAOCP 1.2.2 Exercise 17
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 17. ▶ [ 05 ] What is $\lg 32$? $\log_\pi \pi$? $\ln e$? $\log_b 1$? $\log_b(-1)$? Verified: yes Solve time: 33s By definition (13), $\lg x = \log_2 x$. Therefore $\lg 32 = \log_2 32 = 5,$ since $2^5 = 32$. By definition (9), $\log_b(b) = 1$ for any $b \ne 1$, so $\log_\pi \pi = 1, \qquad \ln e = \log_e e...
TAOCP 1.2.2 Exercise 15
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 15. [ 10 ] Prove or disprove: $$\log_b x/y = \log_b x - \log_b y, \quad \text{if} \quad x, y > 0.$$ Verified: yes Solve time: 29s The statement is true. Since $x,y>0$, Eq. (11) applies to the product $x\cdot(1/y)$. Therefore $$ \log_b!\left(\frac{x}{y}\right) = \log_b!\bigl(x(1/y)\bigr) = \log_b x+\log_b(1/y). $$ Also, by Eq. (12), $$ \log_b!\bigl(y^{-1}\bigr) = (-1)\log_b y = -\log_b y. $$ Substituting...
TAOCP 1.2.3 Exercise 10
Section 1.2.3: Sums and Products Exercise 10. [ 05 ] Is the derivation of Eq. (14) valid even if $n = -2$? Verified: yes Solve time: 3m06s Let $$ S=\sum_{0\le j\le n} ax^j . $$ The derivation of Eq. (14) proceeds by writing $$ xS=\sum_{1\le j\le n+1} ax^j $$ and then subtracting the two sums: $$ S-xS = \sum_{0\le j\le n} ax^j - \sum_{1\le j\le n+1} ax^j . $$ For...
TAOCP 1.2.3 Exercise 11
Section 1.2.3: Sums and Products Exercise 11. [ 03 ] What should the right-hand side of Eq. (14) be if $x = 1$? Verified: yes Solve time: 34s If $x = 1$, the left-hand side of Eq. (14) becomes $\sum_{0 \le j \le n} a = a + a + \cdots + a,$ with exactly $n+1$ terms. Therefore $\sum_{0 \le j \le n} a = a(n+1).$ Hence the right-hand side...
TAOCP 1.2.2 Exercise 11
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 11. ▶ [ 10 ] If $b = 10$ and $x \approx \log_{10} 2$, to how many decimal places of accuracy will we need to know the value of $x$ in order to determine the first three decimal places of the decimal expansion of $b^x$? [ Note: You may use the result of exercise 10 in your discussion.] Verified: yes Solve time: 3m59s...
TAOCP 1.2.2 Exercise 14
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 14. [ 15 ] Prove Eq. (12). Verified: yes Solve time: 44s Solution We are asked to prove Eq. (12), which states: $\log_b(c^y) = y , \log_b c, \quad \text{if } c > 0. \eqno(12)$ Let $b > 0$ and $b \ne 1$ be fixed. By definition, the logarithm $\log_b z$ of a positive real number $z$ is the unique real number $x$...
TAOCP 1.2.2 Exercise 4
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 4. ▶ [ 05 ] What is $(0.125)^{-2/3}$? Verified: yes Solve time: 49s We have $(0.125)^{-2/3}$. First, write $0.125$ as a fraction: $0.125 = \frac{1}{8}.$ Next, apply the definition of a rational exponent, $b^{p/q} = \sqrt[q]{b^p}$: $(1/8)^{-2/3} = \sqrt[3]{(1/8)^{-2}}.$ Raising $1/8$ to the $-2$ power gives $(1/8)^{-2} = 8^2 = 64.$ Taking the cube root yields $\sqrt[3]{64} = 4.$ Therefore, $(0.125)^{-2/3} = \boxed{4}.$
TAOCP 1.2.2 Exercise 6
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 6. [ 10 ] Let $x = m + 0.d_1 d_2 \ldots$ and $y = n + 0.e_1 e_2 \ldots$ be real numbers. Give a rule for determining whether $x = y$, $x < y$, or $x > y$, based on the decimal representation. Verified: yes Solve time: 1m58s Let $$ x=m+0.d_1d_2d_3\cdots,\qquad y=n+0.e_1e_2e_3\cdots, $$ where the decimal representations are taken in the canonical...
TAOCP 1.2.3 Exercise 1
Section 1.2.3: Sums and Products Exercise 1. ▶ [ 10 ] The text says that $a_1 + a_2 + \cdots + a_0 = 0$. What, then, is $a_2 + \cdots + a_0$? Verified: yes Solve time: 34s By definition, a sum of the form $a_1 + a_2 + \cdots + a_0$ is empty because the upper limit is less than the lower limit. According to the conventions in Section 1.2.3,...
TAOCP 1.2.2 Exercise 30
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 30. [ 12 ] Simplify the expression $(\ln x)^{\ln x / \ln \ln x}$, assuming that $x > 1$ and $x \ne e$. Verified: no Solve time: 19s Solution By equation (15), $$ \ln x = \log_e x. $$ Hence $$ (\ln x)^{\ln x / \ln \ln x} = \left(e^{\ln \ln x}\right)^{\ln x / \ln \ln x}. $$ Using the law of exponents...
TAOCP 1.2.2 Exercise 18
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 18. [ 10 ] Prove or disprove: $\log_8 x = \frac{1}{2} \lg x$. Verified: yes Solve time: 26s The statement is true. By the change-of-base formula (14), $\log_8 x = \frac{\log_2 x}{\log_2 8}.$ Since $8 = 2^3$, Eq. (12) gives $\log_2 8 = \log_2 (2^3) = 3 \log_2 2 = 3.$ Therefore $\log_8 x = \frac{\log_2 x}{3} = \frac{1}{3} \lg x.$ Hence $\log_8...
TAOCP 1.2.10 Exercise 1
Section 1.2.10: Analysis of an Algorithm Exercise 1. [ 10 ] Determine the value of $p_{n0}$ from Eqs. (4) and (5) and interpret this result from the standpoint of Algorithm M. Verified: yes Solve time: 40s From (4) with $k=0$ and using $p_{n-1,-1}=0$ from (5), $$ p_{n0}=\frac{1}{n}p_{n-1,-1}+\frac{n-1}{n}p_{n-1,0}=\frac{n-1}{n}p_{n-1,0}. $$ From (5), $p_{10}=1$. Iteration yields $$ p_{n0}=\prod_{j=2}^{n}\frac{j-1}{j} =\frac{1}{n}. $$ The event $A=0$ occurs exactly when no new maximum is encountered in steps...
TAOCP 1.2.1 Exercise 2
Section 1.2.1: Mathematical Induction Exercise 2. ▶ [ 15 ] There must be something wrong with the following proof. What is it? “ Theorem. Let $a$ be any positive number. For all positive integers $n$ we have $a^{n-1} = 1$. Proof. If $n = 1$, $a^{n-1} = a^{1-1} = a^0 = 1$. And by induction, assuming that the theorem is true for $1, 2, \ldots, n$, we have $$a^{(n+1)-1} =...
TAOCP 1.2.1 Exercise 1
Section 1.2.1: Mathematical Induction Exercise 1. [ 05 ] Explain how to modify the idea of proof by mathematical induction, in case we want to prove some statement $P(n)$ for all nonnegative integers, that is, for $n = 0$, $1$, $2$, $\ldots$ instead of for $n = 1, 2, 3, \ldots,$. Verified: yes Solve time: 31s To prove a statement $P(n)$ for all nonnegative integers $n = 0, 1, 2,...