% CHANGES TO VOLUME 2 OF THE ART OF COMPUTER PROGRAMMING % % Copyright (C) 1997,1998,1999,2000,2001,2002,2003, % 2004,2005,2006,2007,2008 by Donald E. Knuth % This file may be freely copied provided that no modifications are made. % All other rights are reserved. % % Three levels of changes to the books are distinguished here: % % "\bugonpage" introduces the correction of an error; % "\amendpage" introduces new material for future editions; % "\improvepage" introduces ameliorations of lesser importance. % % (Changes introduced by \improvepage do not appear in the hardcopy listing.) % % Also, "\planforpage" introduces some of the author's half-baked intentions. % % NOTE: TO PUT THE INDEX ON A SEPARATE PAGE, RUN THIS WITH THE COMMAND LINE % tex "\let\indexeject+ \input err2" \newif\ifall % \alltrue means show the trivial items too \relax % hook \def\vertical{|} \def\inref#1 #{\expandafter\def\csname\vertical#1\endcsname} \catcode`|=\active \let|\inref \input \jobname.ref \catcode`|=12 \input taocpmac % use the format for TAOCP, with modifications below \def\becomes{\ifmmode\ \hbox\fi{\manfnt y}\ } % wiggly arrow indicates a change \def\bugonpage#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt\llap{\manfnt x}% print a black triangle in left margin {\bf Page #2}\enspace #3 \leaders\hrule\hfill\ \eightrm\date#4.} \nobreak\smallskip\iftrue\noindent} \def\amendpage#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt{\bf Page #2}\enspace #3 \leaders\hrule\hfill\ \eightrm\date#4.} \nobreak\smallskip\iftrue\noindent} \def\improvepage#1.#2 #3 (#4) {\ifall \medbreak\ninepoint \line{\kern-6pt{\sl Page #2\enspace #3\/} \leaders\hrule\hfill\ \eightrm\date#4.} \nobreak\smallskip\noindent} \def\planforpage#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt{\bf Page #2}\enspace #3 \leaders\hbox to 5pt{\hss.\hss}\hfill\ \eightrm\date#4.} \nobreak\smallskip\begingroup\let\endchange=\endgroup\sl\noindent} \let\endchange=\fi \def\nl{\par\noindent} \def\nlh{\par\noindent\hangit} \def\hangit{\hangindent2em} \def\cutpar{{\parfillskip=0pt\par}} \def\date#1.#2.#3.{% convert "yy.mm.dd." to "dd Mon 19yy" #3 \ifcase#2\or Jan\or Feb\or Mar\or Apr\or May\or Jun\or Jul\or Aug\or Sep\or Oct\or Nov\or Dec\fi \ \ifnum #1<97 \hundred#1\else19#1\fi} \def\hundred{20} % the "century" for dates before '97 \def\ex #1. [#2]{\ninepoint \textindent{\bf#1.}[{\it#2\/}]\kern6pt} \def\EX #1. [#2]{\ninepoint \textindent{\llap{\manfnt x}\bf#1.}[{\it#2\/}]\kern6pt} \def\foottext#1{\medskip \hrule height\ruleht width5pc \kern-\ruleht \kern3pt \eightpoint \smallskip\textindent{#1}} \def\volheadline#1{\line{\cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill \titlefont\ #1\ \cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill}} \def\refin#1 {\let|\inref \input #1.ref \let|\crossref} \let\defaultpointsize=\tenpoint %%%%%%%%%%%%%% opening remarks %%%%%%%%%%%%%%%%%%%%%%%% \def\lhead{INTRODUCTION} \let\rhead=\lhead \titlepage \volheadline{THE ART OF COMPUTER PROGRAMMING} \bigskip \volheadline{ERRATA TO VOLUME 2 (3rd edition)} \bigskip \noindent This document is a transcript of the notes that I have been making in my personal copy of {\sl The Art of Computer Programming}, Volume~2 (third edition) since it was first printed in 1997. \ifall Four levels of updates\dash---``errors,'' ``amendments,'' ``plans,'' and ``improvements''\dash---appear, indicated by four \else Three levels of updates\dash---``errors,'' ``amendments,'' and ``plans''\dash---appear, indicated by three \fi different typographic conventions: \begingroup\def\hundred{17} \bugonpage 0.666 line 1 (76.07.04) Technical or typographical errors (aka bugs) are the most critical items, so they are flagged with a `\thinspace{\manfnt x}\thinspace' preceding the page number. The date on which I first was told about the bug is shown; this is the effective date on which I paid the finder's fee. The necessary corrections are indicated in a straightforward way. If,~for example, the book says `$n$' where it should have said `$n+1$', the change is shown thus: \smallskip $n$ \becomes $n+1$ \endchange \amendpage 0.666 line 2 (89.07.14) Amendments to the text appear in the same format as bugs, but without the~`\thinspace{\manfnt x}\thinspace'. These are things I wish I had known about or thought of when I wrote the original text, so I added them later. The date is the date I drafted the new text. \endchange \def\hundred{19} \planforpage 0.666 line 3 (17.11.20) Plans for the future represent a third kind of item. In such notes I~sketched my intentions about things that I wasn't ready to flesh out further when I~wrote them down. You can identify these items because they're written in slanted type, and preceded by a bunch of dots `\hbox to 6em{\leaders\hbox to 5pt{\hss.\hss}\hfill}' leading to the date on which I recorded the plan in my files. \endchange \improvepage 0.666 line 4 (38.01.10) The fourth and final category\dash---indicated by page and line number in smaller, slanted type\dash---consists of minor corrections or improvements that most readers don't want to know about, because they are so trivial. You wouldn't even be seeing these items if you hadn't specifically chosen to print the complete errata list in all its gory details. Are you sure you wanted to do that? \endchange \endgroup \ifall\else\medskip\ninepoint My personal file of updates also includes a fourth category of items, not shown in this list. They are miscellaneous minor corrections or improvements that most readers don't want to know about, because they are so trivial. If you really want to see all of the gory details, you can download the full list from Internet webpage $$\.{http://www-cs-faculty.stanford.edu/\char`\~knuth/taocp.html}$$ by selecting the ``long form'' of the errata. \fi \medskip \tenpoint My shelves at home are bursting with preprints and reprints of significant research results that I want to digest and summarize, where appropriate, in the ultimate edition of Volume~2. I didn't do that in the third edition because I would surely have to do it over again later: New results continue to pour forth at a great rate, and I will have time to rewrite that volume only~once. Volumes 4 and~5 need to be finished first. So I've put most of my effort so far into writing up those parts of the total picture that seem to have converged to their near-final form. It follows, somewhat paradoxically, that the updates in this document are most current in the areas where there has been least activity. On the other hand I do believe that the changes listed here bring Volume~2 completely up to date in two respects: (1)~All of the research problems in the previous edition\dash---i.e., all exercises that were rated 46 and above\dash---have received new ratings of 45 or less whenever I learned of a solution; and in such cases, the answer now refers to that solution. (2)~All of the historical information about pioneering developments has been amended whenever new details have come to my attention. \beginconstruction The ultimate, glorious, future editions of Volumes 1--3 are works in progress. Please let me know of any improvements that you think I ought to make. Send your comments either by snail mail to D.~E. Knuth, Computer Science, Gates Building 4B, Stanford University, Stanford CA~94305-9045, or by email to {\tt taocp{\char`\@}cs.stanford.edu}. (Use email for book suggestions only, please\dash---all other correspondence is returned unread to the sender, or discarded, because I have no time to read ordinary email.) Although I'm working full time on Volume~4 these days, I~will try to reply to all such messages within a year of receipt. Current news about {\sl The Art of Computer Programming\/} is posted on $$\.{http://www-cs-faculty.stanford.edu/\char`~knuth/taocp.html}$$ and updated regularly. \par\endconstruction \rightline{\dash---Don Knuth, September 1997} \bigskip \bigskip {\quoteformat Oh! If only someone would give me time, time, time to do everything\/ {\rm properly}, to read everything at\/ {\rm my own\/} tempo, to take it apart and put it together again. \author KARL BARTH (1922) % letter to Edvard Thurneysen, spring 1922 % found in Revolutionary Theology in the Making: Barth-Thurneysen % Correspondence 1914--1925, tr by Jas. D. Smart % Richmond VA: John Knox Press, 1964, p43 \vfill\eject } \def\today{\number\day\space\ifcase\month\or January\or February\or March\or April\or May\or June\or July\or August\or September\or October\or November\or December\fi \space\number\year} %%%%%%%%%%%%%%% CHANGES FOR VOLUME 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\lhead{CHANGES TO VOLUME 2: SEMINUMERICAL ALGORITHMS} \let\rhead=\lhead \titlepage \volheadline{SEMINUMERICAL ALGORITHMS} \bigskip \rightline{Copyright \copyright\ 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004,\qquad} \rightline{2005, 2006, 2007, 2008, Addison\with Wesley; all rights reserved} \rightline{Last updated \today} \bigskip \rightline{\sl Most of these corrections have already been made in recent printings.} \smallskip \let\defaultpointsize=\tenpoint \bugonpage 2.xii line 11 {(``General Test Procedures'')} (97.12.22) \ninepoint 41 \becomes 42 \endchange \amendpage 2.2 a new paragraph near the top (04.02.27) \textindent{f)}{\it Cryptography.}\enspace A source of unbiased bits is crucial for many types of secure communications, when data needs to be concealed.\smallskip\noindent \ninepoint[Now relabel the paragraphs about ``aesthetics'' and ``recreation.''] \endchange \amendpage 2.3 lines 11--13 (04.09.05) [See the articles by Kendall \dots~61. See also S.~H. Lavington's \becomes [F.~N. David describes the early history in {\sl Games, Gods, and Gambling\/} (1962). See also Kendall \dots~61; S.~H. Lavington's \endchange \improvepage 2.5 line 8 (98.10.09) $\lfloor X/10^9\rfloor$ , \becomes $\lfloor X/10^9\rfloor$, \endchange \amendpage 2.9 exercise 19 (05.05.08) \ninepoint [{\it M48\/}] Solve the problems of exercises 11 through 15 \becomes [{\it\HM47\/}] Solve the problems of exercises 11 through 15 asymptotically \endchange \amendpage 2.9 the rating of exercise 21 (07.04.05) \ninepoint [{\it 42}\/] \becomes [{\it 40}\/] \endchange \bugonpage 2.12 line $-4$ (98.10.26) \ninepoint (See exercise 3.) \becomes \endchange \bugonpage 2.16 line 5 (97.12.29) \ninepoint do not to provide \becomes do not provide \endchange \bugonpage 2.17 line 21 (02.01.03) 383--389 \becomes 163--167 \endchange \improvepage 2.17 line $-10$ (98.05.21) \tenpoint {\it then} \becomes {\sl then} \endchange \bugonpage 2.18 line 11 (01.01.26) length $\lambda$ of \becomes length $\lambda$ of the period of \endchange \improvepage 2.20 line 15 (05.11.08) called {\it the order of $a$ modulo $m$} \becomes called the {\it order\/} of $a$ modulo $m$ \endchange \improvepage 2.24 between lines 1 and 2 (98.01.13) [there's a spurious dot near the left margin] \endchange \amendpage 2.26 new copy for exercise 8 (04.02.27) \ninepoint Let $Y_n = \lfloor 10X_n/2^{35}\rfloor$ \dots\ much more often \becomes\nl Let $Y_n = \lfloor 20X_n/2^{35}\rfloor $; then $Y_n$ should be a random integer between 0 and 19, and the triples $(Y_{3n},\ Y_{3n+1},\ Y_{3n+2})$ should take on each of the $8000$ possible values from $(0, 0, 0)$ to $(19, 19, 19)$ with nearly equal frequency. But with 1,000,000 values of $n$ tested, many triples never occurred, and others occurred much more often \endchange \improvepage 2.28 top (97.11.14) [the page number is blurry] \endchange \improvepage 2.28 line 13 (07.10.04) $k\gets55$. \becomes $k\gets55$. (We cannot have both $j=0$ and $k=0$.) \endchange \bugonpage 2.29 line $-15$ (98.01.04) came as shock \becomes came as a shock \endchange \amendpage 2.31 line 8 (06.10.18) Section 7.1 \becomes Section 7.1.3 \endchange \bugonpage 2.33 line $-2$ (97.12.29) from \eq(12) \becomes from \eq(13) \endchange \improvepage 2.39 lines 9 and 10 (01.07.08) Lemma 3.2.1.2Q, the trick of exercise 7 \becomes the results of exercises 7 and 13 \endchange \bugonpage 2.48 line 4 after Fig.~3 (97.11.20) random fracton \becomes random fraction \endchange \improvepage 2.49 in the caption to Fig.~4 (07.12.11) distributions. \becomes distributions. The $x$ value marked ``5\%'' is the percentage point where $F(x)=0.05$. \endchange \improvepage 2.50 in {\eq(11)} (05.02.03) max \becomes sup \qquad(twice) \endchange \improvepage 2.50 line 22 (05.02.03) maximum \becomes least upper bound \endchange \bugonpage 2.54 bottom line (00.02.07) every few microseconds \becomes every few milliseconds \endchange \bugonpage 2.69 line $-2$ (08.04.30) $-6C\_$ \becomes $-6C_1\_$ \endchange \bugonpage 2.72 line 5 (02.04.22) {\bf8} (1990) \becomes {\bf9} (1990) \endchange \improvepage 2.74 line 19 (02.08.22) {\sl Paris\/ \bf81} (1875) \becomes {\bf81} (Paris, 1875) \endchange \bugonpage 2.78 exercise 24 (05.02.03) \ninepoint line 1: [{\it\HM35\/}] \becomes [{\it\HM37\/}]\nl line 7: $N(\alpha)$ \becomes $N(\alpha)^2$ \qquad(twice) \endchange \bugonpage 2.81 replacement for line $-6$ (97.11.08) $$\eqalignno{\noalign{\vskip-10pt} \delta(x)&=\lfloor x\rfloor + 1-\lceil x\rceil = \[\hbox{$x$ is an integer}]; \phantom{\half-\half\delta(x)=x-\half\bigl(\lfloor x\rfloor +\lceil x\rceil\bigr).}&\eq(6)\cr } $$ \endchange \amendpage 2.82 the line following {\eq(10)} (01.06.13) exercise 2 \becomes exercises 1.2.4--38 and 1.2.4--39(a,b,g) \endchange \bugonpage 2.89 line $-13$ (05.07.25) (1978) \becomes (1977) \endchange \bugonpage 2.90 line 4 (99.02.25) $\sum _{j=1}^{@t} a_t$ \becomes $\sum _{j=1}^{@t} a_j$ \endchange \amendpage 2.90 new exercise (01.06.13) \ninepoint \noindent[Renumber exercise 3 as exercise 2, delete the former exercise 2, and insert the following new material:]\smallskip \ex 3. [M23] (N. J. Fine.) Prove that $\bigl\vert\sum_{k=0}^{n-1} ((2^k x+\half))\bigr\vert<1$ for all real numbers $x$. \endchange \improvepage 2.92 exercise 22 (05.02.03) \ninepoint If $x$ is a real number \becomes If $x$ is a random real number, uniformly distributed \endchange \bugonpage 2.92 rating of exercise 23 (99.04.28) \ninepoint[{\it28\/}] \becomes [{\it M28\/}] \endchange \amendpage 2.103 lines 6--8 of step S7 (99.08.25) In hundreds \dots~dimensions. \becomes Usually $\vert z_j\vert\le1$, but L.~C. Killingbeck noticed in 1999 that larger values occur for about 0.00001 of all multipliers when $m=2^{64}$. \endchange \amendpage 2.106 improvement to Table 1 (04.05.02) L. C. Killingbeck has carried out an exhaustive search of all multipliers $a\equiv1$ mod~4 when $m=2^{32}$. He found that the multiplier $a=2650845021$ has $\nu_2^2=4938969760$, $\nu_3^2=2646962$, $\nu_4^2=68342$, $\nu_5^2=8778$, and $\nu_6^2=1506$, so it outperforms the other multipliers listed for this modulus. Indeed, its spectacular $\mu$ scores $(3.61,4.20,5.37,8.85,4.11)$ exceed all values of $\mu_2$, $\mu_3$, $\mu_4$, and $\mu_5$ for any modulus in the entire table. \endchange \bugonpage 2.107 line number 25 of the table (98.11.20) \eightpoint 15.6 \becomes 14.6 \endchange \improvepage 2.109 line $-16$ (02.09.28) p.\ 332 \becomes 332 \endchange \improvepage 2.111 line 1 (01.11.04) (44) \becomes \eq(44) \endchange \improvepage 2.112 in {\eq(49)} (05.02.06) remove the factor $\displaystyle{1\over N}$ \qquad (three times) \endchange \improvepage 2.113 near the top (05.02.06) remove the factors $1/N$ from \eq(52), \eq(53), and the line after~\eq(53); also change $01$} \endchange \bugonpage 2.115 line 1 of exercise 8 (99.02.16) \ninepoint[{\it M16\/}] Line 18 \becomes [{\it M18\/}] Line 10 \endchange \improvepage 2.117 exercise 26 (05.02.06) \ninepoint line 2: $N\_$ \becomes\nl line 3: Where does \dots\ $m=1$? \becomes \endchange \amendpage 2.117 last line of exercise 23 (01.01.05) \ninepoint Alekseev \becomes Alexeev % this is his preference since 1998! \endchange \bugonpage 2.122 line $-4$ (03.09.30) 0.587 \becomes 0.590 \endchange \bugonpage 2.122 replacement for line $-3$ (00.02.07) \textindent{\bf P4.} [Compute $X_1, X_2$.]\enspace If $S=0$, set $X_1\gets X_2\gets 0@$; otherwise set \endchange \improvepage 2.122 line $-2$ (98.12.22) = \ \becomes \ $\gets$\qquad (twice) \endchange \bugonpage 2.124 replacement for Figure 9 (00.02.07) \centerline{\epsfbox{\figdir/ch3.9}} \endchange \improvepage 2.125 lines 6 and 7 after the figure (98.02.25) concave downward, and when $x > 1$ it is concave upward, \becomes concave, and when $x > 1$ it is convex, \endchange \bugonpage 2.127 line $-6$ (99.12.02) $15\le j\le31$ \becomes $16\le j\le31$ \endchange \bugonpage 2.128 in Table 1 (00.07.28) the value of $Y_4$: $-33.13$ \becomes $-33.16$\nl the value of $Y_5$: $-39.55$ \becomes $-39.51$\nl the value of $Y_9$: $0.00$ \becomes\nl the value of $Z_4$: $34.93$ \becomes $34.96$\nl the value of $Z_5$: $41.35$ \becomes $41.31$\nl the value of $Z_9$: $0.00$ \becomes \endchange \bugonpage 2.129 replacement for lines $-3$ and $-2$ (03.09.30) Otherwise set $V$ to a new uniform deviate; and repeat step F4 if the new $V$ is $\le U$. Otherwise (that is, if $K$ is even, in the discussion above), replace $U$ by a new uniform deviate $(.b_0b_1\ldots b_t)_2$ and go back to F3. \endchange \amendpage 2.132 new paragraph following line 15 (05.03.21) With an improved approximation to the acceptance region [see J.~L. Leva, {\sl ACM Trans.\ Math.\ Software\/ \bf18} (1992), 449--455] we can, in fact, reduce the expected number of logarithm computations to only 0.012. \endchange \bugonpage 2.135 line $-16$ (99.03.23) $(1-2\nu)$ \becomes $(1-2/\nu)$ \endchange \improvepage 2.138 line 1 of exercise 3 (00.02.07) \ninepoint{\it dividing\/} by $k$ \becomes computing its {\it remainder\/} mod~$k$ \endchange \improvepage 2.139 exercise 9 (98.02.25) \ninepoint concave downward for $x < 1$, concave upward for $x > 1$? \becomes concave for $x < 1$, convex for $x > 1$? \endchange \bugonpage 2.139 exercise 12 (99.10.19) \ninepoint $f(x)f(y)$ \endchange \amendpage 2.140 bottom line (05.05.19) \ninepoint ${X_1 \lor \bigl( X_2 \land \bigl( X_3 \lor (X_4 \land X_5)\bigr)\bigr)}$ \becomes ${X_1 \bor \bigl( X_2 \band \bigl( X_3 \bor (X_4 \band X_5)\bigr)\bigr)}$ \endchange \amendpage 2.141 line 2 of exercise 27 (06.10.18) \ninepoint Section 7.1 \becomes Section 7.1.3 \endchange \bugonpage 2.141 line 1 of exercise 29 (97.11.10) \ninepoint a simple \becomes Find a simple \endchange \improvepage 2.145 lines $-13$ and $-12$ (01.08.20) division by~$j$ should {\it not\/} be used to determine~$k$ \becomes $k$ should {\it not\/} be computed by taking a remainder modulo~$j$ \endchange \bugonpage 2.146 line 14 (01.03.17) Algorithm S \becomes Algorithm P \endchange \bugonpage 2.147 line 1 of exercise 14 (01.03.09) \ninepoint to sequence \becomes to a sequence \endchange \amendpage 2.148 new exercise (03.11.22) \ninepoint \EX 18. [M32] People sometimes try to shuffle $n$ items $(X_1,X_2,\ldots,X_n)$ by successively interchanging $$X_1\swap X_{k_1},\; X_2\swap X_{k_2},\; \ldots,\; X_n\swap X_{k_n},$$ where the indices $k_j$ are independent and uniformly random between 1 and $n$. Consider the directed graph with vertices $\{1,2,\ldots,n\}$ and with arcs from $j$ to $k_j$ for $1\le j\le n$. Describe the digraphs of this type for which, if we start with the elements $(X_1,X_2,\ldots,X_n)=(1,2,\ldots,n)$, the stated interchanges produce the respective permutations (a)~$(n,1,\ldots,2)$; \ (b)~$(1,2,\ldots,n)$; \ (c)~$(2,\ldots,n,1)$. Conclude that these three permutations are obtained with wildly different probabilities. \endchange \amendpage 2.148 quotation to follow the exercises (06.03.24) {\quoteformat By means of the thread one understands the ball of yarn, % Que por el hilo se sacar\'a el ovillo, so we'll be satisfied and assured by having this sample. % y quedaremos con esto satisfechos, y seguros, % y vuestra merced quedar\'a contento y pagado. \author MIGUEL DE CERVANTES, {\sl El Ingenioso Hidalgo Don Quixote de la Mancha\/} (1605) % book 1, chapter 4, lines 1513--1516 in the "old spelling control edition" PQ6323 A1 1988 v1 } \endchange \improvepage 2.155 line $-2$ (02.03.22) H.\enspace S. \becomes H. S. \endchange \improvepage 2.164 line 4 (02.08.22) {\sl Paris\/ \bf A285} (1977) \becomes {\bf A285} (Paris, 1977) \endchange \bugonpage 2.173 line 16 (97.11.30) 0000, 0001, 1101, or 1110; \becomes 0000, 0011, 1101, or 1110; \endchange \amendpage 2.173 line $-7$ (01.06.23) Walsh transform \becomes Hadamard transform \endchange \improvepage 2.176 top (00.01.14) line 2: per year \becomes per Gregorian year\nl line 3: per second \becomes per Gregorian second \endchange \bugonpage 2.176 line $-19$ (03.01.25) $3R\approx600000$ \becomes $\approx3R=600000$ \endchange \bugonpage 2.176 line $-16$ (05.09.20) 53.5 teraMIP-years \becomes 535 teraMIP-years \endchange \amendpage 2.177 lines 11--13 (00.01.11) {\it normal\/} \dots\ 216. \becomes {\it entirely normal\/} to base~$b$, and he stated Theorem~C informally without apparently realizing that it required proof [{\sl Rendiconti Circ.\ Mat.\ Palermo\/ \bf27} (1909), 247--271, \S12.] \endchange \amendpage 2.179 lines 21--23 (05.08.08) Finally Levin \dots analyzing Algorithm L. \becomes Finally Charles Rackoff refined the methods of that paper by introducing and analyzing Algorithm~L [see L.~Levin, {\sl J.~Symbolic Logic\/ \bf58} (1993), 1102--1103]. \endchange \amendpage 2.179 lines 25--26 (00.03.20) [{\sl STOC\/ \bf21} (1989), 12--24; {\bf22} (1990), 395--404] \becomes [{\sl SICOMP\/ \bf28} (1999), 1364--1396] \endchange \amendpage 2.179 lines 27--28 (04.02.27) not surveyed here \dots\ practical random number generation. \becomes beyond the scope of this book. \endchange \bugonpage 2.182 line 2 of exercise 31 (02.12.26) \ninepoint $U_n<\half$ \becomes $U_j<\half$ \endchange \bugonpage 2.183 line 7 of exercise 42 (01.01.26) \ninepoint $k$-bit vectors, \becomes $k$-bit vectors, with $c\ne c'$, \endchange \improvepage 2.185 near the bottom (01.02.18) line $-4$: {\tt (long)(MM/AA)} \becomes {\tt MM / AA}\nl line $-2$: {\tt (long)(X/QQ)} \becomes {\tt (X/QQ)} \endchange \improvepage 2.186 near the top (01.02.18) line 8: {\tt (long)(MMM/AAA)} \becomes {\tt MMM / AAA}\nl line 10: {\tt (long)(Y/QQQ)} \becomes {\tt (Y/QQQ)} \endchange \improvepage 2.186 replacement for line $-10$ (02.01.01) {\tt void ran\char`\_array(long aa[],int n) \char`\{ /* put n new values in aa */} \endchange \improvepage 2.187 line 8 (02.01.01) [delete this line, since it is now redundant] \endchange \amendpage 2.187 replacement for lines 12--35 (02.01.01) \vskip-17pt\begintt register long ss=(seed+2)&(MM-2); for (j=0;j=MM) ss-=MM-2; /* cyclic shift 29 bits */ } x[1]++; /* make x[1] (and only x[1]) odd */ for (ss=seed&(MM-1),t=TT-1; t; ) { for (j=KK-1;j>0;j--) x[j+j]=x[j], x[j+j-1]=0; /* "square" */ for (j=KK+KK-2;j>=KK;j--) x[j-(KK-LL)]=mod_diff(x[j-(KK-LL)],x[j]), x[j-KK]=mod_diff(x[j-KK],x[j]); if (is_odd(ss)) { /* "multiply by z" */ for (j=KK;j>0;j--) x[j]=x[j-1]; x[0]=x[KK]; /* shift the buffer cyclically */ x[LL]=mod_diff(x[LL],x[KK]); } if (ss) ss>>=1; else t--; } for (j=0;j0$, go to step~P5. \endchange \bugonpage 2.395 near the bottom (98.12.18) line $-10$: about $n$ \becomes about its input\nl line $-9$: certified a billion different primes \becomes tested a billion different numbers \endchange \improvepage 2.395 line $-6$ (00.02.07) cosmic radiations \becomes cosmic radiation \endchange \amendpage 2.396 upper middle (05.03.19) line 11: first proposed \becomes proposed\nlh line 16: 35--36]. \becomes 35--36], and independently discovered by J.~L. Selfridge. \endchange \amendpage 2.396 middle (05.04.28) \indent A completely different \dots purely of theoretical interest. \becomes\nl \indent A completely rigorous and deterministic way to test for primality in polynomial time was finally discovered in 2002 by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, who proved the following result: \thbegin Theorem A. {\sl Let $r$ be an integer such that $n\perp r$ and the order of $n$ modulo~$r$ exceeds $(\lg n)^2$. Then $n$ is prime if and only if the polynomial congruence $$(z+a)^n\;\equiv\;z^n+a\qquad\hbox{\rm (modulo $z^r-1$ and $n$)}$$ holds for $0\le z\le\sqrt r\,\lg n@$.} (See exercise 3.2.2--11(a).)\quad\slug \smallskip An excellent exposition of this theorem has been prepared by Andrew Gran\-ville [{\sl Bull.\ Amer.\ Math.\ Soc.\ \bf42} (2005), 3--38], who presents an elementary proof that it yields a primality test with running time $\Omega(\log n)^6$ and $O(\log n)^{11}$. He also explains a subsequent improvement due to H.~Lenstra and C.~Pomerance, who showed that the running time can be reduced to $O(\log n)^{6+\epsilon}$ if the polynomial $z^r-1$ is replaced by a more general family of polynomials. And he discusses refinements by P. Berrizbeitia, Q.~Cheng, P.~Mih\u{a}ilescu, R.~Avanzi, and D.~Bernstein, leading to a probabilistic algorithm by which a proof of primality can almost surely be found in $O(\log n)^{4+\epsilon}$ steps whenever $n$ is prime. \endchange \improvepage 2.398 replacement for lines 5 and 6 {(see the following change)} (01.07.02) \vbox{\ninepoint \halign to \hsize{\hfil#\tabskip0pt plus 10pt &$\rt{#}$&$\rt{#}$&$\rt{#}$&$\rt{#}$&$\rt{#}$&$\rt{#}$&$\lft{#}$\tabskip0pt\cr After E1:&876&\phantom073&12&\phantom{00}5329&1&\hbox{---}& \phantom{159316^2 \equiv +2^4 \cdot 3^2 \cdot 5^1}\cr}} \endchange \improvepage 2.398 lines 1--5 of step E1 (01.07.02) $R'\gets2R$, \dots, $n\mod2$. \becomes $R^{@\prime} \gets 2R$, $U' \gets R^{@\prime}$, $V \gets D - R^2$, $V' \gets 1$, $A\gets\lfloor R'/V\rfloor$, $U \gets R'-(R'\mod V)$, $P^{@\prime} \gets R$, $P \gets (AR+1)\mod N$, $S \gets 1$. (This algorithm follows the general procedure of exercise 4.5.3--12, finding the continued fraction expansion of $\sqrt{kN}$. The variables $U\!@$, $U'$, $V\!@$, $V'$, $P$, $P^{@\prime}$, $A$, and $S$ represent, respectively, what that exercise calls $\lfloor\sqrt D\rfloor + U_n$, $\lfloor\sqrt D\rfloor + U_{n-1}$, $V_n$, $V_{n-1}$, $p_n\mod N\!@$, $p_{n-1}\mod N\!@$, $A_n$, and $n\mod 2$, where $n$~is initially~1. \endchange %\bugonpage 2.402 line $-3$ or $-4$ (05.05.27) %square root \becomes $\sqrt8$th root %\endchange \amendpage 2.402 bottom line (98.05.14) factors. \becomes factors. An excellent exposition of this method has been given by Joseph~H. Silverman and John~Tate in {\sl Rational Points on Elliptic Curves\/} (New York:\ Springer, 1992), Chapter~4. \endchange \amendpage 2.403 line $-19$ (99.07.07) {\bf67} (1998), to appear \becomes {\bf68} (1999), 429--451 \endchange \amendpage 2.403 line $-9$ (00.06.20) to appear \becomes {\sl Math.\ Comp.\ \bf69} (2000), 1297--1304 \endchange \improvepage 2.404 line $-12$ (00.02.07) take cube roots \becomes take cube roots quickly \endchange \amendpage 2.406 line 5 (99.07.07) considered \becomes published \endchange \amendpage 2.407 after line 10 (99.07.07) % first used in 7th printing \indent\em Historical note: It was revealed in 1998 that Clifford Cocks had considered encoding messages by the transformation $x^{pq}\mod pq$ already in 1973, but his work was kept secret. \endchange \improvepage 2.409 line 10 (99.08.26) Joel Armengaud \becomes Jo\"el Armengaud \endchange \planforpage 2.409 update on Mersenne primes (04.05.02) Tens of thousands of people have joined the GIMPS project, and Scott Kurowski has provided Internet software called PrimeNet to make the exponent assignments more systematic. Already in February 1998, more than one year's worth of computing was being done each day looking for Mersenne primes, and the amount of activity was growing steadily. Thus we can expect gradual progress on the hunt for these historic numbers.\par I will list all Mersenne primes found after 1997 here, but on page 409 of the printed books I'll abbreviate the following information because space is tight. I won't update page 409 with every new printing, but I did make major amendments when preparing the 15th printing. So far the new primes $2^p-1$ found are: $$\vcenter{\halign{\hfil#&&\quad#\hfil\cr $p$\hfil&Discoverer&Date found\cr \noalign{\vskip2pt} 3021377&Roland Clarkson&27 January 1998\cr % assigned on 12 December 1997 6972593&Nayan Hajratwala&1 June 1999\cr % 111 days idle time; conf 23 June 13466917&Michael Cameron&14 November 2001\cr % 45 days; conf 3 Dec 20996011&Michael Shafer&17 November 2003\cr % about 14 days, 2GHz Pentium 4; conf 2 Dec 24036583&Josh Findley&May 2004\cr % 14 days, 2.4 GHz Pentium 4; announced 28 May 25964951&Martin Nowak&Feb 2005\cr % 50 days, 2.4 GHz Pentium 4; announced 27 Feb 30402457&Curtis Cooper,Steven Boone&Dec 2005\cr% ~50 days, campus computer; ann 24 Dec 32582657&Curtis Cooper,Steven Boone&4 Sep 2006\cr%verified by 16 Itaniums in six days; ann 9/11 }}$$ \endchange \amendpage 2.412 near the top (05.01.08) lines 2 and 3: are prime [see \dots\ 136]. \becomes are prime.\nlh line 6: other forms. \becomes other forms. [See E.~Picutti, {\sl Historia Math.\ \bf16} (1989), 123--136; Hugh~C. Williams, {\sl \'Edouard Lucas and Primality Testing\/} (1998), Chapter~2.] \endchange \improvepage 2.412 line 1 of exercise 11 (98.04.20) \ninepoint 197209, \ $k=5$, $m=1$ \becomes 197209, $k=5$, $m=1$ \endchange \improvepage 2.413 line 2 of exercise 22 (02.04.21) \ninepoint given $n$ \becomes when $n$ is an odd integer $\ge3$. \endchange \improvepage 2.414 line 1 (98.04.20) \ninepoint of \ $t$ primes \becomes of $t$ primes \endchange \bugonpage 2.416 line 11 of exercise 41 (98.01.21) \ninepoint $f(1000,10)$ \becomes $f_2(1000,10)$ \endchange \bugonpage 2.416 line 3 of exercise 43 (01.04.27) \ninepoint $y\in S_m$ \becomes $y\in Q_m$ \endchange \bugonpage 2.424 line 18 (00.10.28) Pablo Nu\~nez \becomes Pedro Nu\~nez \endchange \bugonpage 2.432 line 2 after {\eq(22)} (98.06.23) $b_6^3 \cdot b_6^3 \cdot b_6^3$ \becomes $b_6^3 \cdot b_6^3$ \endchange \improvepage 2.434 line 21 (02.08.22) (Paris:\ 1835) \becomes (Paris, 1835) \endchange \bugonpage 2.436 line 7 of exercise 17 (00.03.03) \ninepoint $\deg(u)$ \becomes $\deg(U)$ \endchange \bugonpage 2.442 line 14 (98.03.06) {\sl P\v{e}stov\'ani\/} \becomes {\sl P\v{e}stov\'an{\'\i}} \endchange \bugonpage 2.442 line $-4$ (99.06.06) 3,~,\dots \becomes 3,~\dots \endchange \amendpage 2.449 near the top (00.07.20) \hangit lines 5--8: A faster \dots\ arithmetic \becomes Faster algorithms for distinct-degree factorization when $p$ is very large have been found by J.~von zur~Gathen, V.~Shoup, and E.~Kaltofen; the running time is $O(n^{2+\epsilon}+n^{1+\epsilon}\log p)$ arithmetic\nlh lines 10--11: [See \dots\ to appear.] \becomes [See {\sl Computational Complexity\/ \bf2} (1992), 187--224; {\sl J.~Symbolic Comp.\ \bf20} (1995), 363--397; {\sl Math.\ Comp.\ \bf 67} (1998), 1179--1197.] \endchange \improvepage 2.449 middle (02.08.22) line 15: {\sl Paris\/} (1785) \becomes (Paris, 1785)\nl lines 24--25: {\sl Sci.\ Paris}, series 2, {\bf35} (1866) \becomes {\sl Sci.}, series 2, {\bf35} (Paris, 1866)\nl line 34: {\sl Paris\/ \bf A291} (1980) \becomes {\bf A291} (Paris, 1980) \endchange \amendpage 2.449 bottom line, and top of page 450 (02.06.17) extended by an astronomer \dots von Schubert's method independently \becomes extended by N.~Bernoulli in 1708 and, more explicitly, by an astronomer named Friedrich von Schubert in 1793, who showed how to find all factors of degree~$n$ in a finite number of steps; see M.~Mignotte and D.~\c{S}tef\u{a}nescu, {\sl Revue d'Hist.\ Math.\ \bf7} (2001), 67--89. L.~Kronecker rediscovered their approach independently, \endchange \bugonpage 2.451 line $-13$ (00.10.28) the range $(-{169\over 2},{169\over2})$ \becomes the range $(-{169\over 2}\dts{169\over2})$ \endchange \bugonpage 2.455 lines 27 and 28 (98.09.30) {\sl Efficient Polynomial Computations\/} \becomes {\sl Effective Polynomial Computation\/} \endchange \bugonpage 2.457 line 3 of exercise 20 (98.02.05) \ninepoint $u(x) = (x - \alpha )@u(x)$ and $v(x) = (\bar \alpha x - 1)@u(x)$ \becomes $u(x) = (x - \alpha )@w(x)$ and $v(x) = (\bar \alpha x - 1)@w(x)$ \endchange \bugonpage 2.458 line 11 (98.04.14) \ninepoint \def\\#1{{\bf#1}} whenever $v_\\j\ne0$.\ \becomes whenever $u_\\j\ne0$. \endchange \bugonpage 2.458 line 20 (99.06.06) \ninepoint $1^1$ \becomes $1^2$ \endchange \bugonpage 2.459 line 3 of exercise 29 (01.05.01) \ninepoint $1/2-1/(2p^d)$ \becomes $1/2-1/(2p^{2d})$ \endchange \bugonpage 2.461 line $-18$ (04.09.21) before 200~\BC.\ in Pi\:ngala's Hindu classic {\sl Chanda\d{h}s\=utra\/} \becomes before \AD.~400 in Pi\:ngala's Hindu classic {\sl Chanda\d{h}\'s\=astra\/} \nl [also change ``next 1000 years'' to ``next several centuries'', a few lines down] \endchange \improvepage 2.462 better wording in step A2 (03.01.24) Set $N$ \dots~skip \becomes Set $t\gets N\mod2$ and $N \gets \lfloor N\!/2\rfloor$. If $t=0$, skip \endchange \improvepage 2.464 line $-2$ (01.02.17) $100,000$ \becomes 100,000 \endchange \improvepage 2.465 line $-6$ (00.02.07) Our goal \becomes Thus $l(1)=0$, $l(2)=1$, $l(3)=l(4)=2$, etc. Our goal \endchange \amendpage 2.466 line 3 (05.12.02) 179 \becomes 179, 199 \endchange \amendpage 2.466 lines 19--21 (08.05.25) Furthermore, as E. G. Thurber \dots\ steps earlier. \becomes Furthermore, we can omit all the even numbers (except 2) in the first row, if we bring values of the form $d_j/2^e$ into the computation $e$ steps earlier. [See E.~^{Wattel} and G.~A. ^{Jensen}, {\sl Math.\ Centrum Report\/ \rm ZW1968-001} (1968), 18~pp.; E.~G. ^{Thurber}, {\sl Duke Math.\ J. \bf40} (1973), 907--913.] \endchange \bugonpage 2.470 line 28 (98.09.20) $2^m + 2^{m+1} + 2^{d+1} + 2^d$ \becomes $2^m + 2^{m-1} + 2^{d+1} + 2^d$ \endchange \improvepage 2.475 line 14 (06.10.23) the multisets $M_{ij}$ and $S_i$, \becomes the multisets $M_j$, $S_i$, $M_{ij}$ \endchange \improvepage 2.477 line 15 (02.06.30) {\sl des math.} \becomes {\sl des Math.} \endchange \amendpage 2.477 line 23 (05.09.15) 948 cases \becomes 102 cases \endchange \amendpage 2.477 line 28 (07.05.08) Kevin \becomes Neill Clift found in 2007 that $l(n)=l(2n)=l(4n)=31$ when $n=30958077$. Kevin \endchange \amendpage 2.477 replacement for the bottom ten lines (08.05.27) $$\vcenter{\halign{\hfil$#$&\quad\hfil$#$\cr r&c(r)\kern-.3em\cr\noalign{\vskip2pt} 1&2\cr 2&3\cr 3&5\cr 4&7\cr 5&11\cr 6&19\cr 7&29\cr 8&47\cr 9&71\cr 10&127\cr 11&191\cr }}\qquad\qquad\qquad\vcenter{\halign{\hfil$#$&\quad\hfil$#$\cr r&c(r)\cr\noalign{\vskip2pt} 12&379\cr 13&607\cr 14&1087\cr 15&1903\cr 16&3583\cr 17&6271\cr 18&11231\cr 19&18287\cr 20&34303\cr 21&65131\cr 22&110591\cr }}\qquad\qquad\qquad\vcenter{\halign{\hfil$#$&\quad\hfil$#$\cr r&c(r)\cr\noalign{\vskip2pt} 23&196591\cr 24&357887\cr 25&685951\cr 26&1176431\cr 27&2211837\cr 28&4169527\cr 29&7624319\cr 30&14143037\cr 31&25450463\cr 32&46444543\cr 33&89209343\cr }}$$ \endchange \bugonpage 2.478 line 4 (99.02.01) [The \becomes The \endchange \amendpage 2.478 line 5 (08.05.27) Bleichenbacher. \becomes Bleichenbacher, and $c(29)$ through $c(33)$ by Neill Clift. \endchange \amendpage 2.478 replacement for lines 19--25 (08.05.24) \noindent table lists the first few values of $d(r)$, according to Flammenkamp and Clift: $$\vcenter{\halign{\hfil$#$&&\enspace\hfil$#$&\quad\enspace\hfil$#$\cr r&d(r)\kern-.6em&r&d(r)\kern-.1em&r&d(r)&r&d(r)\kern.25em &r&d(r)\kern.5em&r&d(r)\kern.75em\cr \noalign{\vskip2pt} 1&1& 6&15& 11&246& 16&4490 &21&90371 &26&1896704\cr 2&2& 7&26& 12&432& 17&8170 &22&165432 &27&3501029\cr 3&3& 8&44& 13&772& 18&14866 &23&303475 &28&6465774\cr 4&5& 9&78& 14&1382& 19&27128 &24&558275 &29&11947258\cr 5&9& 10&136& 15&2481& 20&49544 &25&1028508 &30&22087489\cr }}$$ \endchange \amendpage 2.478 the three lines following {\eq(49)} (08.05.27) Computer calculations \dots for $n=32$. \becomes Computer calculations by Neill Clift show that $l(2^n-1)$ is exactly equal to $n-1+l(n)$ for $1\le n\le46$; and E. G. Thurber [{\sl Discrete Math.\ \bf 16} (1976), 279--289] has shown that several of these values, including the case $n = 32$, can actually be calculated by hand. \endchange \improvepage 2.479 line 4 after Table 1 (03.12.27) certain of the elements \becomes some of the elements \endchange \amendpage 2.479 lines $-23$ thru $-20$ (05.09.17) The chain \dots~theorem due to Hansen: \becomes Hansen pointed out that the chain constructed in Theorem~F is an $l^{@0}$-chain (see exercise~22); and he also established the following improvement of Eq.~\eq(50): \endchange \amendpage 2.479 new lines to be inserted at the bottom (05.09.17) \indent Computations by Neill Clift have shown that $l(n)0$? Does equality always~hold?\tighten \endchange \improvepage 2.489 line $-14$ (99.06.07) $n-1$ divisions \becomes $n-1$ divisions, since $v_n=u_n$ \endchange \bugonpage 2.493 line 5 (99.06.07) $\lceil n/2\rceil$ \becomes $\lceil n/2\rceil-1$ \endchange \improvepage 2.501 line 3 after {\eq(38)} (97.11.13) [remove the thin line above ``F. Yates''] \endchange \amendpage 2.502 lines 8--18 (01.06.23) line 8: the {\it Walsh transform\/} \becomes the {\it Hadamard transform\/} or the {\it Walsh transform\/}\nlh line 9: by J. L. Walsh \becomes by J. Hadamard [{\sl Bull.\ Sci.\ Math.\ \rm(2) \bf17} (1893), 240--246] and by J. L. Walsh\nlh lines 16--18: (See H. F. Harmuth, \dots\ Walsh coefficients.) \becomes (See Section 7.2.1.1 for further discussion of the Hadamard--Walsh coefficients.) \endchange \bugonpage 2.504 replacement for bottom line (99.06.28) $$u_{[n]}(x)= \Bigl({y_0w_0\over x-x_0}+\cdots+{y_nw_n\over x-x_n}\Bigr)\Big/ \Bigl({w_0\over x-x_0}+\cdots+{w_n\over x-x_n}\Bigr),\eqno(45)$$ \endchange \bugonpage 2.507 replacement for bottom line, in 4th printing only (99.10.10) $$ \def\1{$@\overline{\?1\!@}@@$} A=\!\left(@\vcenter{\halign{#\cr 1 0 \1 0 0 1 \1\cr 0 1 0 0 0 1 0\cr 0 0 1 0 1 \1 1\cr 0 0 0 1 1 \1 1\cr }}@\right)\!,\quad B=\!\left(@\vcenter{\halign{#\cr 1 0 0 \1 \1 0 1\cr 0 1 0 1 0 0 0\cr 0 0 1 1 1 0 \1\cr 0 0 \1 \1 0 1 1\cr }}@\right)\!,\quad C=\!\left(@\vcenter{\halign{#\cr 1 1 0 0 0 0 0\cr 1 0 1 1 0 0 1\cr 1 0 0 0 1 1 1\cr 1 0 1 0 1 0 1\cr }}@\right)\!. \eqno(53)$$ \endchange \bugonpage 2.521 line 2 of exercise 56 (00.04.26) \ninepoint $\tau_{ijk}x_ix_k$ \becomes $\tau_{ijk}x_ix_j$ \endchange \bugonpage 2.521 line 3 of exercise 60 (01.01.26) \ninepoint and only \becomes and only if \endchange \bugonpage 2.522 line 14 (02.04.21) \ninepoint problems of size $m\times n\times s$ \becomes problems of the respective sizes $m\times n\times s$ and $s\times m\times n$ \endchange \bugonpage 2.523 line 15 of exercise 67 (99.06.28) \ninepoint $))\bigr)$ \becomes $)\bigr)$ \endchange \bugonpage 2.529 a spurious line just before Algorithm N (05.02.07) N \becomes \qquad(this error appeared in the 15th, 16th, and 17th printings only) \endchange \bugonpage 2.531 line 7 (99.08.09) $U=$ \becomes $U(z)=$ \endchange \improvepage 2.536 line 1 of exercise 26 (02.06.30) \ninepoint $U_2z^2\cdots{}$ \becomes $U_2z^2+\cdots$ \endchange \let\defaultpointsize=\ninepoint % get ready for answer pages \improvepage 2.539 line 8 (06.11.22) horse. \becomes horse (unless you know, say, the jockey). \endchange \amendpage 2.539 line 10 of answer 6 (05.06.08) $f(x) = ax$.] \becomes $f(x) = ax$. See G.~Frobenius, {\sl Sitzungsberichte preu{\ss}ische Akademie der Wissenschaften\/} (1895), 82--83.] \endchange \amendpage 2.539 simplification for line $-10$ (98.06.11) $\lambda \delta_{\mu0}+\mu+\lambda -1-\left((\mu+\lambda -1)\mod \lambda \right)$ \becomes $\lambda\bigl(\lceil\mu/\lambda\rceil+\delta_{\mu0}\bigr)$ \endchange \amendpage 2.540 line 12 (02.12.25) $e(n)=$ \becomes $e(n)=\rho(n+1)=$ \endchange \improvepage 2.540 line $-2$ (02.11.09) that $\lambda = 1, \mu = 1$, or $\lambda = 2, \mu = 0$, is \becomes that $(\mu,\lambda)=(1,1)$ or that $(\mu,\lambda)=(0,2)$ is \endchange \improvepage 2.541 line 9 of answer 12 (03.07.12) {\sl its Applications} \becomes {\sl Its Applications} \endchange \amendpage 2.542 new answer (05.05.08) \ans19. Clearly Pr(no final cycle has length~1)${}=(m-1)^m\!/m^m$. R.~Pemantle [{\sl J.~Algorithms\/ \bf54} (2005), 72--84] has shown that $\Pr(\lambda=1)=\Theta(m^{k/2})$, and that $\Pr((\mu+\lambda)^2>2m^kx$ and $\lambda/(\mu+\lambda)\le y)$ rapidly approaches $ye^{-x}$, when $x>0$, $01$, we can also replace $N$ by $N\mod(m/d)$. [And {\it delete\/} the first sentence, `When $m=1$, \dots~zero.'] \endchange \bugonpage 2.584 line 4 of answer 3 (01.08.20) $U>k\lfloor m/k\rfloor$ \becomes $U\ge k\lfloor m/k\rfloor$ \endchange \improvepage 2.585 improvement to Fig.~A--4 (05.12.04) $$\epsfbox{\figdir/ch3.2004}$$ \endchange \bugonpage 2.585 line $-3$ (99.10.04) absolute minimum \becomes absolute maximum \endchange \improvepage 2.587 replacement for lines $-13$ and $-12$ (99.06.29) \vskip-5pt \algindentset{\hskip\parindent B1} \algstep B2. [Iterate.] If $U \ge r$, set $N \gets N + 1$, $q \gets q(1 - p)(t - 1 + N)/N\!@$, $r \gets r + q$, and repeat this step. Otherwise return $N$ and terminate.\quad\slug \endchange \bugonpage 2.587 bottom line (05.02.03) $\textstyle{2\over5}(a-bu)-{2\over3}$ \becomes $\textstyle{2\over5}(a-bu)-{2\over3}a$ \endchange \bugonpage 2.588 line 1 (05.02.03) $I=\int_0^{a/b}u\sqrt{a-bu}\,du={4\over15}a^{5/2}\!/b^2$ \becomes $I=2\int_0^{a/b}u\sqrt{a-bu}\,du={8\over15}a^{5/2}\!/b^2$ \endchange \bugonpage 2.588 line $-2$ of answer 21 (05.02.03) $E=\int_0^{r(x)}$ \becomes $E=2\int_0^{r(x)}$ \endchange \improvepage 2.588 last line of answer 22 (99.06.29) 208]. \becomes 208.] \endchange \amendpage 2.588 beginning of answer 25 (05.05.19) line 1: $\lor$ \becomes $\bor$\nl line 2: $\land$ \becomes $\band$ \endchange \bugonpage 2.589 line 3 of answer 29 (06.03.25) David Seneschol \becomes David Seneschal \endchange \amendpage 2.590 end of answer 31 (99.07.08) Preprint \dots~1997) \becomes {\sl Lecture Notes in Comp.\ Sci.\ \bf1470} (1998), 1--20 \endchange \bugonpage 2.591 in printings 5--14 only (04.02.07) [the top line of page 591 was a duplicate of the bottom line of page 590] \endchange \bugonpage 2.591 lines $-3$ and $-2$ of answer 8 (99.06.29) decrease $n$ and $N$ by~1 \becomes set $n\gets n-1$, $N\gets N-X-1$, \endchange \bugonpage 2.592 line 2 of answer 13 (08.01.01) $(x+1)$ \becomes $(x-1)$ \endchange \amendpage 2.592 new answer (03.11.22) \ans18. (a) Oriented trees that essentially merge $(1,2,\ldots{})$ with $(n,n-1,\ldots{})$, such as $$\epsfbox{\figdir/aux.2222}$$ (b) Collections of 1-cycles and 2-cycles. (c) Binary search trees on the keys $(1,2,\ldots,n)$, with $k_j$ the parent of~$j$ (or $j$, at the root); see Section 6.2.2. The number of $(k_1,\ldots,k_n)$ in each case is (a)~$2^{n-1}$; (b)~$t_n\ge \sqrt{n!}$, see 5.1.4--\eq(40); (c)~${2n\choose n}{1\over n+1}$. [Case~(a) represents the least common permutation; case~(b) represents the most common, when $n\ge18$. See D.~P. Robbins and E.~D. Bolker, {\sl {\AE}quationes Mathematic\ae\/ \bf22} (1981), 268--292; D.~Goldstein and D.~Moews, {\sl {\AE}quationes Mathematic\ae\/ \bf65} (2003), 3--30.] \endchange \bugonpage 2.593 line 1 of answer 6 (05.03.19) By exercise 5 \becomes By exercise 4 \endchange \improvepage 2.596 line $-5$ (99.06.29) . We \becomes We \endchange \bugonpage 2.599 line 1 of answer 9 (01.01.26) The values \becomes (a) The values \endchange \amendpage 2.601 replacement for lines 15--41 (02.01.01) \vskip-17pt\begintt 1 CONTINUE X(2)=X(2)+1 SS=SSEED T=TT-1 10 DO 12 J=KK,2,-1 X(J+J-1)=X(J) 12 X(J+J-2)=0 DO 14 J=KKK,KK+1,-1 X(J-(KK-LL))=X(J-(KK-LL))-X(J) IF (X(J-(KK-LL)) .LT. 0) X(J-(KK-LL))=X(J-(KK-LL))+MM X(J-KK)=X(J-KK)-X(J) IF (X(J-KK) .LT. 0) X(J-KK)=X(J-KK)+MM 14 CONTINUE IF (MOD(SS,2) .EQ. 1) THEN DO 16 J=KK,1,-1 16 X(J+1)=X(J) X(1)=X(KK+1) X(LL+1)=X(LL+1)-X(KK+1) IF (X(LL+1) .LT. 0) X(LL+1)=X(LL+1)+MM END IF \endtt \endchange \amendpage 2.602 {(now page 601)} two new lines before `\.{END}' (02.01.01) \vskip-17pt\begintt DO 22 J=1,10 22 CALL RNARRY(X,KKK) \endtt \endchange \amendpage 2.602 line 8 of answer 11 (02.01.01) copy in {\it ul\/} \becomes copy in $x$ \endchange \amendpage 2.602 from line 28 of answer 11 to that answer's end (02.01.01) \vskip-17pt\begintt double ss=2.0*ulp*((seed&0x3fffffff)+2); |intt|smallskip for (j=0;j=1.0) ss-=1.0-2*ulp; /* cyclic shift of 51 bits */ } x[1]=1; u[1]+=ulp; /* make u[1] (and only u[1]) "odd" */ for (s=seed&0x3fffffff,t=TT-1; t; ) { for (j=KK-1;j>0;j--) x[j+j]=x[j],u[j+j]=u[j],x[j+j-1]=0,u[j+j-1]=0.0; /* "square" */ for (j=KK+KK-2;j>=KK;j--) { x[j-(KK-LL)]=x[j]^x[j-(KK-LL)], u[j-(KK-LL)]=mod_sum(u[j-(KK-LL)],u[j]); x[j-KK]=x[j]^x[j-KK],u[j-KK]=mod_sum(u[j-KK],u[j]); } if (is_odd(s)) { /* "multiply by z" */ for (j=KK;j>0;j--) x[j]=x[j-1],u[j]=u[j-1]; x[0]=x[KK],u[0]=u[KK]; /* shift the buffer cyclically */ x[LL]=x[KK]^x[LL],u[LL]=mod_sum(u[LL],u[KK]); } if (s) s>>=1; else t--; } for (j=0;j k_j$ \becomes\nl any doubly infinite sequence of integers with $k_{j+1} > k_j$ and $k_0=0$. \endchange \improvepage 2.606 line 3 of answer 18 (03.06.09) $y_1$, $y_2$, $\ldots$ \becomes $\{y_1,y_2,\ldots{}\}$ \endchange \bugonpage 2.606 line 13 of answer 18 (03.06.09) $\vert x\vert $ and $\vert y\vert $ are fixed \becomes $\vert x\vert $ and $\vert y\vert $ are sufficiently small \endchange \bugonpage 2.607 line 2 of answer 21 (99.08.26) the test \becomes the text \endchange \bugonpage 2.607 line 3 of answer 21 (07.01.26) the systems \becomes the system \endchange \bugonpage 2.608 last line of answer 24 (01.01.26) digits.] \becomes digits. \endchange \improvepage 2.608 line $-2$ of answer 25 (07.01.26) $aaaaa$ \becomes $a$ \endchange \amendpage 2.608 bottom line (05.06.03) induction. \becomes induction. [A.~D. Booth, in {\sl Quarterly J. Mechanics and Applied Math.\ \bf4} (1951), 236--240, applied this principle to two's complement multiplication.] \endchange \bugonpage 2.610 last two lines of answer 31{(c)} (07.01.26) $2^{-\mu}u$ is an integer. \becomes $2^ru$ is an integer, for sufficiently large~$r$. \endchange \amendpage 2.611 replacement for answer 1 (99.01.28) \ans1. $N = (62, +.60\ 22\ 14\ 00)$; $h = (37, +.66\ 26\ 10\ 00)$. Note that the quantity $10h$ would be $(38, +.06\ 62\ 61\ 00)$. \endchange \bugonpage 2.611 line 3 of answer 5 (00.05.02) $x \sim y$ \becomes $bx \sim by$ \endchange \bugonpage 2.612 line 2 of answer 12 (06.03.28) we have $1/b<$ \becomes we have $1/b\le$ \endchange \bugonpage 2.613 line 4 of answer 16 (02.03.22) (1963) \becomes (1962) \endchange \bugonpage 2.613 replacement for answer 19 (02.11.10) \ans19. $\!\bigl( 73 -\bigl(5-\[{\rm rounding\ digits\ are}\ {b\over2}@0 \ldots 0]\bigr) \bigl(6-\[{\rm magnitude\ is\ rounded\ up}]\bigr) + \[e_v\!<\!e_u] + \[{\rm first\ rounding\ digit\ is}\ {b\over2}] - \[{\rm fraction\ overflow}] - 10\[{\rm result\ zero}] +7\[{\rm rounding\ overflow}] +7N +\bigl(3+(16+\[{\rm result\ negative}])\[{\rm opposite\ signs}]\bigr)@X \bigr) u$, where $N$ is the number of left shifts during normalization, and $X$ is the condition that rX receives nonzero digits and there is no fraction overflow. The maximum time of $84u$ occurs for example when $$u = -50\ 01\ 00\ 00\ 00,\quad v = +45\ 49\ 99\ 99\ 99,\quad b = 100.$$ [The average time, considering the data in Section 4.2.4, will be less than $47u$.] \endchange \bugonpage 2.614 line 3 of answer 14 (07.03.01) $b^{2-p}$ \becomes $(1+b^2)b^{-p}$ \endchange \bugonpage 2.615 line 1 of answer 16 (07.03.01) 101.11111 \becomes 101.11110 \endchange \amendpage 2.615 line $-1$ (03.06.27) For another \becomes Kahan observed that $s_n\ominus c_n=\sum_{k=1}^n(1+\phi_k)x_k$ where $\vert\phi_k\vert\le2\epsilon+O((n+1-k)\epsilon^2)$. For another \endchange \amendpage 2.616 line 1 (00.01.27) can combine them \becomes may be able to match them up \endchange \bugonpage 2.616 line 5 of answer 21 (99.09.09) $e_u=e_u=p$ \becomes $e_u=e_v=p$ \endchange \bugonpage 2.617 line 1 of answer 27 (98.07.31) $1\oslash u)\oslash u$ \becomes $1\oslash (1\oslash u)$ \endchange \improvepage 2.622 line 14 of answer 18 (02.03.22) $p(b^{n-1}a\!@,@b^n)$ \becomes $p(b^{n-1}a,@b^n)$ \endchange \bugonpage 2.622 answer 19 (99.09.27) line 1: $\log 10F_n$ \becomes $\log_{10}F_n$\nl line 2: $\log 10\phi$ \becomes $\log_{10}\phi$ \endchange \amendpage 2.625 last line of answer 22 (03.04.07) $b=10$.) \becomes $b = 10$. Similarly, when $b=2^{16}$ we can let $u=(\.{7fff800100000000})_{16}$, $v=(\.{800080020005})_{16}$.) \endchange \bugonpage 2.625 replacement for answer 23 (98.01.23) \textindent{\bf23.}Obviously $v\lfloor b/(v+1)\rfloor<(v+1)\lfloor b/(v+1)\rfloor\le b$; and the lower bound certainly holds if $v\ge b/2$. Otherwise $v\lfloor b/(v+1)\rfloor\ge v(b-v)/(v+1)\ge(b-1)/2>\lfloor b/2\rfloor-1$. \endchange \bugonpage 2.626 replacement for lines 1--5 of answer 25 (98.01.23) \textindent{\bf25.}\mixans\mixfive 002&&ENTA&1&1\cr \hskip\parindent 003&&ADD&V+N-1&1\cr 004&&STA&TEMP&1\cr 005&&ENTA&1&1\cr 006&&JOV&1F&1&Jump if $v_{n-1}=b-1$.\cr 007&&ENTX&0&1\cr 008&&DIV&V+N-1&1&Otherwise compute $\lfloor b/(v+1)\rfloor$.\cr 009&&JOV&DIVBYZERO&1&Jump if $v_{n-1} = 0$.\cr 010&1H&STA&D&1\cr\endmix\nl [All subsequent line numbers for Program D should now be increased by 4.] \endchange \bugonpage 2.627 line 1 (98.02.25) convex function \becomes concave function \endchange \amendpage 2.629 last lines of answer 40 (00.12.28) [See T. Jebelean, \dots\ 459.]\ \becomes [See A.~Sch\"onhage and E. Vetter, {\sl Lecture Notes in Comp.\ Sci.\ \bf855} (1994), 448--459; W.~Krandick and T.~Jebelean, {\sl J.~Symbolic Computation\/ \bf21} (1996), 441--455.] \endchange \amendpage 2.629 line 5 of answer 41 (06.05.02) trial divisor.) \becomes trial divisor. To compute~$w'$ when $b$ is a power of~2, notice that if $w_0w'\equiv1$ (modulo $2^e$) then $w_0w''\equiv1$ (modulo $2^{2e}$) when $w''=(2-w_0w')w'$, by the 2-adic analog of ``Newton's method.'') \endchange \improvepage 2.629 line 10 of answer 41 (98.08.10) signed-magnitude \becomes signed magnitude \endchange \bugonpage 2.630 answer 43 (05.11.08) $xy/255$ \becomes $uv/255$ \qquad(twice) \endchange \bugonpage 2.631 displayed formula in answer 5 (99.05.31) $\scriptscriptstyle\rm p\ prime$ \becomes $\scriptscriptstyle p\ \rm prime$ \endchange \amendpage 2.631 new sentence at end of answer 5 (00.12.05) Replacing 100 by 256 and allowing even moduli gives $2^83^55^3\ldots251^1\approx1.67\cdot10^{109}$. \endchange \amendpage 2.632 last line of answer 14 (03.04.07) 324.] \becomes 324. For improved error bounds, and extensions to moduli of the form $k\cdot2^n\pm1$, see Colin Percival, {\sl Math.\ Comp.\ \bf72} (2002), 387--395.] \endchange \bugonpage 2.632 line 4 of answer 1 (99.11.11) [shift `$+03$' one column to the left] \endchange \improvepage 2.635 line 2 of answer 1 (02.04.08) $B_j$ system \becomes $B_J$ system \endchange \bugonpage 2.636 replacement for answer 9 (06.05.14) % improves 03.10.13 \ans9. Let $p_k=2^{2^{k+2}}$. By induction on $k$ we have $v_k(u)\le{16\over5} (1-1/p_k)(\lfloor u/2\rfloor+1)$; hence $\lfloor v_k(u)/16\rfloor\le \lfloor\lfloor u/2\rfloor/5\rfloor=\lfloor u/10\rfloor$ for all integers $u\ge0$. Furthermore, since $v_k(u+1)\ge v_k(u)$, the smallest counterexample to $\lfloor v_k(u)/16\rfloor=\lfloor u/10\rfloor$ must occur when $u$ is a multiple of~10.\par Now let $u=10m$ be fixed, and suppose $v_k(u)\mod p_k=r_k$ so that $v_{k+1}(u)=v_k(u)+(v_k(u)-r_k)/p_k$. The fact that $p_k^2=p_{k+1}$ implies that there exist integers $m_0$, $m_1$, $m_2$, \dots~such that $m_0=m$, $v_k(u)=(p_k-1)@m_k+x_k$, and $m_k=m_{k+1}p_k+x_k-r_k$, where $x_{k+1}= (p_k+1)x_k-p_kr_k$. Unwinding this recurrence yields $$v_k(u)=(p_k-1)@m_k+c_k-\sum_{j=0}^{k-1}p_jr_j\prod_{i=j+1}^{k-1}(p_i+1), \qquad c_k=3\,{p_k-1\over p_0-1}.$$ Furthermore $v_k(u)+m_k=v_{k+1}(u)+m_{k+1}$ is independent of~$k$, and it follows that $v_k(u)/16=m+(3-m_k)/16$. So the minimal counterexample $u=10y_k$ is obtained for $0\le k\le4$ by setting $m_k=4$ and $r_j=p_j-1$ in the formula $y_k={1\over16}(v_k+m_k-c_0)$. In hexadecimal notation, $y_k$~turns out to be the final $2^k$ digits of \.{434243414342434}.\par Since $v_4(10y_4)$ is less than $2^{64}$, the same counterexample is also minimal for all $k>4$. One way to work with larger operands is to modify the method by starting with $v_0(u)=6\lfloor u/2\rfloor+6$ and letting $c_k=6(p_k-1)/(p_0-1)$, $m_0=2m$. (In effect, we are truncating one bit further to the right than before.) Then $\lfloor v_k(u)/32\rfloor= \lfloor u/10\rfloor$ when $u$ is less than $10z_k$, for $1\le k\le7$, where $z_k={1\over32}(v_k+m_k-6)$ when $m_k=7$, $r_0=14$, and $r_j=p_j-1$ for $j>0$. For example, $z_4=\.{1c342c3424342c34}$. [This exercise is based on ideas of R. A. Vowels, {\sl Australian Comp.\ J. \bf24} (1992), 81--85.] \endchange \amendpage 2.638 last two lines of answer 18 (99.04.15) % also corrects a bug (Is this \dots\ $10^4$?) \becomes (The {\it smallest\/} example is actually round$((.1111111001)_2\cdot2^{784})=.1011\cdot10^{236}$, round$(.1011\cdot10^{235})=(.11111110010)_2\cdot2^{784}$, found by Fred~J. Tydeman.) \endchange \amendpage 2.638 answer 4.5.1--1 (02.01.15) positive. \becomes positive. (See also the answer to exercise 4.5.3--39.) \endchange \bugonpage 2.641 last line of answer 10 (04.02.18) for arbitrary $f$ and $g$, when $m\le n$. \becomes when $m\le n$, $f(m)=O(m)$, and $g(n)=O(n)$. \endchange \bugonpage 2.641 first line of answer 14 (04.02.18) $(2^p-1)$ \becomes $(p^2-1)$ \endchange \bugonpage 2.642 line 2 of answer 17 (01.09.29) $u'=1$ \becomes $u'=u$ \endchange \amendpage 2.645 new answer (08.05.23) \ans32. Yes: See G. Maze, {\sl J. Discrete Algorithms\/ \bf5} (2007), 176--186. \endchange \amendpage 2.645 new answer (98.01.30) \ans34. Brigitte Vall\'ee [{\sl Algorithmica\/ \bf22} (1998), 660--685] has found an elegant and rigorous analysis of Algorithm~B, using an approach quite different from that of Brent. Indeed, her methods are sufficiently different that they are not yet known to predict the same behavior as Brent's heuristic model. Thus the problem of analyzing the binary gcd algorithm, now solved rigorously for the first time, continues to lead to ever more tantalizing questions of higher mathematics. \endchange \amendpage 2.645 lines 4 and 5 of answer 36 (05.08.03) $u =\max(a_{n+2},2a_{n+1})$ and $v=a_{n+3}-u$ \becomes $u =a_{n+2}$ and $v=u+(-1)^n$ \endchange \bugonpage 2.646 in answer 39 (98.06.29) line 1 of step Y6: if $t_1<0$ \becomes if $t_1\le0$\nl line 2 after step Y6: $-u$ after \becomes $-u$, $0% \GC76:77:-3:62% G6510 <000000000001c0000000000700000001f00000000007c0000001fc0000000007f0000001% ff0000000007fc000001ff0000000007fc000001ff0000000007fc000001fe0000000007% f8000001f80000000003e0000001f80000000003e0000001f80000000003e0000001f800% 00000003e0000001f80000000003e0000001f80000000003e0000001f8000e000003e000% 0001f8001f003803e0000001f8003fc03e03e0f00001f8007fe03f83e0fdfffffffffff0% 3fe3e0fffffffffffff03fe3e0fff801f80000003fe3e0ff8001f80000003fc3e07f8001% f80000003f03e07e0001f80000003f03e07e0001f80000003f03e07e0001f80000003f03% e07e0001f80000003f03e07e0001f80000003f03e07e0001f80000003f03e07e0001f800% 00003f03e07e0001f80000003f03e07e0001f80700003f03e07e0001f81f80003f03e07e% 0001f83fc0003f03e07effffffffe0003f03e07e7ffffffff0003f03e07e7ffffffff800% 3f03e07e23c0003ff0003f03e07e01c0003ff0003f03e07e01c0003f80003f03e07e00e0% 003f00003f03e07e00e0007f00003f03e07e00e0007e00003f03e07e0070007e00003f03% e07e007000fe00003f03e07e007000fc00003f03e07e003801fc00003f03e07e003801f8% 00003f03e07e003c01f800003f03e07e001e03f000003f03e07e001e03f000003f03e07e% 000f07e000003f03e7fe000f0fe000003f03fffe000f9fc000003f03fffe00079fc00000% 3fffff7e0007bf8000003ffffc7e0003ff000000fffff07e0003fe000000ffff007e0003% fe0000007ff000780001fc0000003f8000700003fe0000003e0000400007ff8000001000% 0000000fffe0000000000000001fdff8000000000000003f8ffe000000000000007f07ff% c0000000000001fe03fff0000000000003fc01ffffc0000000000ff800ffffe000000000% 1fe0003fffe000000000ff80001fff8000000003fe000007ff000000001ff8000001fc00% 000000ffc00000007800000003ff00000000100000001ff800000000000000001f000000% 0000000000001000000000000000>%% Unicode char "5c90 ), 396. % 18th Chinese mathematics, 197--198, 287, 340--341, 486. % 9th Chinese remainder theorem, 285--290, 389, 404, 584. % 20th \sub for polynomials, 440, 456, 509--510. % 20th Clarkson, Roland Hunter, 409. % 15th Clift, Neill Michael, 477--479, 485. % 22nd Cocks, Clifford Christopher, 407. % 9th Codes for difficulty of exercises, xi. % 4th Cohen, Henri Jos\'e, 345, 658, 687, 712. % 18th Collenne, Joseph D\'esir\'e, 201. % 5th Concave function, 125, 139, 245, 627. % 4th Convex function, 125, 139, 245, 684. % 4th Convolution polynomials, \see Poweroids. % 12th Cooper, Curtis Niles, 409. % 20th Cryptography, 2, 193, 403--407, 415, 417, 505. % 15th David, Florence Nightingale, 3, 566. % 16th Datta, Bibhutibhusan ({\bg\C105\C098\C038\C041\C105\C116\C038\C041\C087\C044\ \C100\C191}) = Bidy\=aranya, Swami ({\bg Sv\C059im\ ibd\C042\C059r\C044\C042}), 343, 461. % 20th de La Vall\'ee Poussin, Charles Jean Gustave Nicolas, 381. % 9th; wrong 7th-8th Dellac, Hippolyte, 465. % 9th Dieter, Ulrich Otto, 89, 91, 92, 101, 114, 116, 119, 129--130, 132, 134, 137, 573, 574, 588. % 10th Diophantus of Alexandria ({\grk Di'ofantos Alexandre'us}), \see Diophantine equations. % 24th Dirichlet, Johann Peter Gustav Lejeune, 342. % 13th Discrete Fourier transforms, 169, 305--311, 316--318, 501--503, 506, 512, 516, 520--521, 524, 595. % 21st Dual of an addition chain, 481, 484, 485. % 19th $e$, as ``random'' example, 21, 33, 47, 52, 108. % 11th Eckhardt, Roger Charles, 189. % 4th Eichenauer-Herrmann, J\"urgen, 32, 558, 559. % 10th Eudoxus of Cnidus, son of {\AE}schinus ({\grk E>'udoxos A>isq'inou uaggelist'hs}), 735. % 4th Maze, G\'erard, 645. % 23rd Metropolis, Nicholas Constantine ({\grk Mhtr'opol$\?$hs, Nik'olaos Kwnstant'inou}), 4, 189, 240, 242, 327. % 23rd Mignotte, Maurice, 450, 683. % 11th Mih\u{a}ilescu, Preda-Mihai, 396. % 18th Miller, James (= Jimmy) Milton, 108. % 7th Minus zero, 202, 244--245, 249, 268, 274. % 8th mod $m$ arithmetic, division, 354, 445, 499; \also Inverse modulo~$m$. % 20th Moews, David John, 593. % 15th Moses, Joel, 454--455. % 4th Multiplication, two's complement, 608. % 19th %Nakamula, Ken (\JC41:48:-4:40% J3570 %<00003000000000003c00000000003e00000000003e00000000003c00000000003c000000% % 00003c00000000003c00000000003c00000000003c000000c0003c000600f0003c000f00% % ffffffffff80ffffffffff80f0003c000f00f0003c000f00f0003c000f00f0003c000f00% % f0003c000f00f0003c000f00f0003c000f00f0003c000f00f0003c000f00f0003c000f00% % f0003c000f00f0003c000f00f0003c000f00f0003c000f00ffffffffff00ffffffffff00% % f0003c000f00f0003c000f00f0003c00060060003c00000000003c00000000003c000000% % 00003c00000000003c00000000003c00000000003c00000000003c00000000003c000000% % 00003c00000000003c00000000003c00000000003c00000000003c000000000018000000% % >%% Unicode char "4e2d %\JC48:48:0:40% J3428 %<007000001c00007c00001f00003e00001f80003e00000f80003c00000f00003c00000f00% % 003c00000f00003c00000f00003c00000f00003c00000f00003c30000f0c003c78000f1e% % fffffcffffff7ffffc7fffff003c00000f00003c00000f00003c00000f00003c00000f00% % 007f00000f00007fc0000f0000fcf0c00f0000fcf8e00f0000fc7c780f0001fc3c7c0f00% % 01fc3c3e0f0003fc183e0f0003bc001f0f0007bc001f0f00073c000f0f000f3c000e0f00% % 1e3c00000f003c3c00000f00f03c00000f00c03c00000f00003c00000f00003c00000f00% % 003c00000f00003c00000f00003c00000f00003c00000f00003c00000f00003c00000f00% % 003c00000f00003c00000f00003c0001ff00003c0000ff00003c00007e00001800003c00% % >%% Unicode char "6751 %\JC48:48:0:40% J2391 %<000003000000040003c000000c0003e0000c0c0003c0001e1fffffffffff1fffffffffff% % 3c000300001e7c0003c0001c7c0003e00c3cf80003c01e38f8ffffffff30707fffffff20% % 000003c00000000003c01800000003c03c00007ffffffe00003ffffffe00000003c00000% % 000003c0000c000003c0001effffffffffff7fffffffffff000000000000030000000180% % 03c0000003c003ffffffffe003ffffffffe003c0780f03c003c0780f03c003c0780f03c0% % 03c0780f03c003c0780f03c003ffffffffc003ffffffffc003c0000003c0018307c00180% % 0003c1f000000043e0f803f00043e0fc00fc00c3c07c107e01c3c07c103e03c3c038183f% % 07c3c000381f1f83e0007c0e3f83fffffc003f03fffffc003e01fffff8001c00fffff000% % >%% Unicode char "61b2 %), 698. % 11th N\=ar\=aya\d{n}a Pa\d{n}\d{d}ita, \vadjust{\vskip1pt}son of N\d{r}si\:mha\indexbreak({\dn nArAyZ pE\char23Xt}, {\dn n\llap{\lower.12em\hbox{\char2}\kern.4em}Es\llap{\char92\kern-.05em}h-y p\llap{\lower.15em\hbox{\char0}\kern.3em}/,}), 387. % 20th Newton, method for rootfinding, 278--279, 312, 486, 529, 629, 719. % 20th Nicomachus of Gerasa ({\grk Nik'omaqos ek~Ger'aswn}), 659. % 4th Nowak, Martin R\period, 409. % 18th Nussbaumer, Henri Jean, 521, 710. % 5th Nystrom, John William, 201. % 5th Oliveira e Silva, Tom\'as Ant\'onio Mendes, 386. % 10th Organ-pipe order, 378. % 22nd Packing, 109. % 20th Palmer, John Franklin, 222. % 5th Pemantle, Robin Alexander, 542. % 18th Percival, Colin Andrew, 632. % 13th Pi ($\pi$), 41, 151, 158, 161, 198, 200, 209, 279--280, 284, 358, 726--727, 733. % 11th \sub as ``random'' example, 21, 25, 33, 47, 52, 89, 103, 106, 108, 184, 238, 243, 252, 324--325, 593, 599, 665. % 15th Pigeonhole principle, 286. % 20th Pi\:ngala, \=Ac\=arya ({\dn aA\char99A\hbox{y\kern-0.3em\hbox{\char13}} Ep\char189l}), 461. % 7th Planck, Karl Ernst Ludwig Marx (= Max), constant, 214, 227, 238, 240. % 23rd Polynomial, resultant, 433, 674, 690. % 5th Potency, 24--26, 36, 47, 52, 73, 83, 87--88, 92, 105, 184. % 13th Powers, Don Michael, 312. % 12th Quolynomial chains, 498, 524, 704--705. % 8th Rackoff, Charles Weill, 179. % 19th Reitwiesner, George Walter, 213, 280. % 9th Rejection method, 125--126, 128--129, 134, 138, 139, 591. % 23rd Resultant of polynomials, 433, 674, 690. % 5th Robbins, David Peter, 593. % 15th Rosi\'nska, Izabela Gra\:zyna, 198. % 21st Rozier, Charles Preston, 324. % 5th RSA box, 404, 406. % 11th Ruler function $\rho(n)$, 540. % 12th Saxena, Nitin ({\dn EnEtn s?s\llap{\char3}nA}), 396. % 18th Scholz\with Brauer conjecture, 478--479, 485. % 11th Sch\"onhage, Arnold, 292, 302--303, 305, 306, 311, 317, 328, 470, 484, 500, 522, 629, 638, 656, 672, 696, 715. % 10th Sch\"onhage\with Strassen algorithm, 306--311, 317. % 10th Schubert, Friedrich Theodor von, 450. % 11th Selfridge, John Lewis, 394, 396, 412, 665. % 18th Seneschal, David, 589. % 20th Seroussi Blusztein, Gadiel ({\heb\Hyy/\Hss/\Hvv/\Hrr/\Hss/ \Hll/\Haa/\Hyy/\Hdd/\Hgg/}), 712. % 16th Shafer, Michael William, 409. % 15th Shamir, Adi ({\heb\Hrr/\Hyy/\Hmm/\Hsh/ \Hyy/\Hdd/\Hai/}), 403, 405, 416, 505, 599, 669. % 10th Shokrollahi, Mohammad Amin \indexbreak ({\arab\Afam/\Amh/\Ail/\Aa/\Afr/\Amc/\Aish/ \Afn/\Amy/\Aim/\Aa/ \Afd/\Amm/\Amhh/\Aim/}), 515. % 11th Shukla, Kripa Shankar ({\dn k\kern-0.6em\hbox{\char2}\kern0.5empA \hbox{f\kern-0.6em\raise0.4em\hbox{\char21}}kr f\kern-0.3em\lower.05em\hbox{\char0}\kern0.2em\char63lA}), 208, 648. % 8th Sideways addition, 463, 466. % 19th Sierpi\'nski, Wac{\l}aw Franciszek, 666. % 19th Signed magnitude representation, 202--203, 209--210, 247, 266. % 4th Sikdar, Kripasindhu ({\bg\C107\C128\C112\C059\C105\C115\C'264\C040\ \C105\C120\C107\C100\C059\C114}), 327. % 21st Silverman, Joseph Hillel, 402. % 4th Singh, Parmanand ({\dn prmAn\kern-0.6em\raise0.4em\hbox{\char21}d Es\kern-0.6em\raise0.4em\hbox{\char21}h}), 387. % 20th \.{SLB} (shift left rAX binary), 339, 340. % 4th Smirnov, Nikolai Vasilievich ({\rus Smirnov, Nikolai0 Vasilp1evich}), 57. % 10th Squares, sum of two, 579--580. % 6th \.{SRB} (shift right rAX binary), 339, 340, 481. % 4th Stahnke, Wayne Lee, 31. % 4th Star chains, 467, 473--477, 480, 482. % 5th Steele, Guy Lewis, Jr\period, 635--636, 638. % 10th \c{S}tef\u{a}nescu, Doru, 450. % 11th Stern, Moritz Abraham, 654. % 4th Sturm, Jacques Charles Fran\c{c}ois, 434, 438, 674. % 9th Subbarao, Mathukumalli Venkata\indexbreak ({\tl\|1128|\C101\\1\|3128|\C86\C135\\1\C184\\7\|1128|\C101\\1\|1177|\C222\ \|{-1}141|\C107\\1\C9\\{-1}\|1128|\C71\\2\C81\ \|1128|\C110\C135\\1\C99\\{-3}\C130\\{-2}\C171\|{-1}129|\C103\\4\|0107|\|1128|\\2\C210}), 469. % 13th Subnormal floating point numbers, 246. % 21st Tarski (Tajtelbaum), Alfred, 718. % 20th Tate, John Torrence, Jr\period, 402. % 4th Totient function $\varphi(n)$, 19--20, 289, 369, 376, 583, 646. % 12th Trabb Pardo, Luis Isidoro, 661. % 8th Trinomials, 32, 40, 572. % 21st Two's complement notation, 15, 188, 203--204, 228, 275--276, 608. % 19th Tydeman, Frederick John, 638. % 4th Ulam, Stanis{\l}aw Marcin, 138, 140, 189. % 10th Vall\'ee, Brigitte, 352, 355, 366, 644, 645. % 4th von Schubert, Friedrich Theodor, 450. % 11th von zur Gathen, Joachim Paul Rudolf, 449, 611, 673, 687. % 7th Walker, Alastair John, 120, 127, 139. % 4th Wattel, Evert, 466. % 23rd Welford, Barry Payne, 232. % 11th White, Jon L, 635--636, 638. % 10th Williams, Hugh Cowie, 380, 390, 394, 401, 412, 415, 661, 664. % 18th Winograd, Shmuel, 280, 316, 500, 501, 507, 509, 512--514, 520, 523, 705--707, 710, 712, 714. % 11th \.{WM1} (word size minus one), 252, 267, 613. % 10th Wolff von Gudenberg, J\"urgen Freiherr, 242. % 4th Wunderlich, Charles Marvin\sic/, 390, 394, 399--400. % 11th Zero, minus, 202, 244--245, 249, 268, 274. % 8th \vfill \enddoublecolumns \endchange \bye [The next printing will be the 23rd.] not listed above: the change to page 388 was omitted in printings of 2005--2007; put it in 23rd page 483, bottom line, six -> seven page 638, answer 18: style of "Case 1" and "Case 2" changed for conformity page 702, answer 24: style of "Case 1" and "Case 2" changed for conformity ARTICLES "TO APPEAR" THAT ARE STILL PENDING: