Errata for the book "Modern Computer Arithmetic" up to 8 September 2010. Note: an error in a given version might also be present in previous versions. We only mention it in the most recent version. Version 0.2 (June 2008, 190 pages): ================================== Page 72: in the second addition chain for e=15, "2 + 2 = 3" should read "1 + 2 = 3" [reported by Mark Wezelenburg, 18 February 2009] Page 161: Algorithm SinCos, line 9: for C_j, the '+' sign should be '-' [reported by Mark Wezelenburg, 18 February 2009] Version 0.2.1 (23 March 2009, 215 pages): ======================================== Pages 13 and 14 were left blank Version 0.3 (11 June 2009, 221 pages): ===================================== Page 22, line -12: "satisfies and M(2n)" should read "satisfies M(2n)" [reported by Marc Mezzarobba, 28 October 2009] Page 22, line -12: "M(2n) ~ M(n)" should read "M(2n) ~ 2M(n)" [reported by anonymous referee, 7 September 2009] Page 26, Theorem 1.4.1: the complexity should be O(n (m+1)) instead of O(n m), since for example for m=0 we need to read A, B to check whether A >= B (consider the case A = B - 1). [reported by Guillaume Hanrot, 12 October 2009] Page 53, line -4: change "near from" to "close to". [reported by Wolfgang Ehrhardt, 4 July 2009] Page 57, line -2: the O(M(d log n)) complexity for the Kronecker-Schonhage substitution is wrong; it should be O(M(d (log n + log d))) since the product coefficients are bounded by d n^2. [reported by anonymous referee, 7 September 2009] Page 113, line 12: Change "know" to "now". [reported by Wolfgang Ehrhardt, 4 July 2009] Page 115, Lemma 3.4.3: add the premise $\mu \le B$ to ensure that B_1 is nonzero. [reported by Wolfgang Ehrhardt, 4 July 2009] Page 120, Algorithm 48, step 5: remove redundant parentheses. [reported by Wolfgang Ehrhardt, 4 July 2009] Page 129, line -10, "Vetter. [152]," should read "Vetter [152]." Page 132, we say "most modern processors only implement multiplication in hardware, and division and square root are microcoded, using Newton's method". This is not completely right, since only those processors with a fused multiply-add (FMA) can use Newton's method; other processors are using the SRT algorithm [reported by Jean-Michel Muller, 30 June 2009] Page 169, line -4: "We need theta..." should read "We need the theta..." [reported by Joerg Arndt, 4 August 2009] Page 190, line 17: "4.38 -4.40" should read "4.38-4.40" [reported by Wolfgang Ehrhardt, 4 July 2009] Page 204, reference [84]: the version should read "4.3.0" and the year "2009" [reported by Wolfgang Ehrhardt, 4 July 2009] Page 208, reference [136]: change "Thmas" to "Thomas". [reported by Wolfgang Ehrhardt, 4 July 2009] Page 211, reference [164]: the author "Nico Temme Tom Koornwinder" should be "Tom Koornwinder, Nico Temme". [reported by Wolfgang Ehrhardt, 4 July 2009] Page 211, reference [170]: the first "s" in "Vepstas" should be have an accent [reported by Wolfgang Ehrhardt, 4 July 2009] Page 219: index entries for "Sorenson" should be merged. [reported by Wolfgang Ehrhardt, 4 July 2009] Version 0.4 (11 November 2009, 239 pages): ========================================= Page 5, line 11: "Sidimohamed" should read "Sidi Mohamed" [reported by Sidi Mohamed Sedjelmaci, 12 November 2009] Page 19, line 8: "B <= ceil(T/2)" should read "B <= floor(T/2)" Page 19, second paragraph: taking d in {0, 1} does not work with our convention for div/mod. One should take d in {-1, 0} instead. [reported by Wolfgang Ehrhardt, 15 November 2009] Page 20, Algorithm 1.2 BasecaseMultiply, Step 2: "do do" should read "do" Page 26, Algorithm OddEvenKaratsuba, remove the line "A_0 <- A mod x^k, A_1 <- A div x^k" Page 26, line 15: "depend" should read "depends" Page 30, line 6: "This formula perform" should read "This formula performs" Page 35, line 1: in "say Q_1, of k words ... mainly depends on the k most...", replace k by m-k Page 40, Algorithm 1.1: one should add the input condition gcd(c,beta)=1 [reported by Wolfgang Ehrhardt, 15 November 2009] Page 42, Algorithm 1.12 SqrtRem: BasecaseSqrtRem is undefined, it should be a base-case implantation of the algorithm. [reported by Wolfgang Ehrhardt, 15 November 2009] Page 48, line -2: "at line 4" should read "at Step 1" (the line which computes c = a/b mod m, since there are no line numbers) Page 49, line 4: "plus possible" should read "plus possibly" Page 49, line -10: remove "(step 6)" and "(step 12)" Page 52, line 4, "if k = 0" should read "If k = 0" Page 52, line -1: add "(for their odd part)" at the end of the sentence Page 53, line -14: replace "we multiply S by (b',r)" by "we multiply 2^{-2j_2}S by (b',r)" Page 53, line -7, replace "integer reconstruction" by "rational reconstruction" [reported by Emmanuel Thome, 10 February 2010] Page 54, line 1, replace "-a/u" by "a/u" [reported by Emmanuel Thome, 10 February 2010] Page 58, Exercise 1.18, line 2: replace "two set" by "two sets" Page 58, Exercise 1.19, replace "steps 9-11" by "steps 6-8" Page 65, Section 2.1.3, line 4, replace "are computed" by "is computed" Page 65, Section 2.1.4, line 2, replace "bit" by "bits" Page 66, lines 3 and 6: the second Z in "Z/nZ" should be identical to the first [reported by Wolfgang Ehrhardt, 15 November 2009] Page 66, end of Section 2.2, a space is missing before "at the cost" [reported by Sidi Mohamed Sedjelmaci, 12 November 2009] Page 70, Algorithm 2.3: the output vector \^{a} should read \v{a} [reported by Wolfgang Ehrhardt, 15 November 2009] Page 71, line 2: the symbol \v{a} should be bold [reported by Wolfgang Ehrhardt, 15 November 2009] Page 72, Algorithm FFTMulMod, step 10: replace \omega^{K-1} by \omega Page 74, line -8: replace "MSB-variant" by "LSB-variant" Page 76, line 7: remove an extra space before "3" Page 76, Section 2.4.2, 2nd sentence, add "with \lambda an integer constant such that gcd(N,\lambda)=1" Page 77, line 3: replace "c_i = 0" by "the next value of c_i is 0" Page 82, line -3: replace "the iteration Eq. (4.5)" by "the iteration (4.5)" Page 83, line 1: replace "x_{k+1}" by "x_{j+1}", and add "mod p^k" at the end of the previous sentence Page 84, "the following algorithm is usually faster:" corresponds to Algorithm MultipleInversion which appears before! [reported by Wolfgang Ehrhardt, 15 November 2009] Page 87, lines 6 and 7: replace "n" by "\ell" Page 88, Algorithm BaseKExp, step 1: remove "a^2 then" Page 88, line 17: remove "and" before "Algorithm BaseKExp" [reported by Wolfgang Ehrhardt, 15 November 2009] Page 88, lines 17-18: replace "Algorithm BaseKExp performs one multiplication to precompute a^2" by "... two multiplications to precompute a^2 and a^3" Page 88, line -8: "This leads to the following algorithm:" should read "This leads to Algorithm BaseKExpOdd." [reported by Wolfgang Ehrhardt, 15 November 2009] Page 89, Algorithm BaseKExpOdd, step 1, replace "Precompute" by "Precompute a^2 then" Page 89, Algorithm BaseKExpOdd, step 3: if e_{\ell} is even >= 4, the value t[e_{\ell}] is not defined. Do the same as in steps 5-6. Page 90, Section 2.7, line 4: a dot (.) is missing after "(CRT)" Pages 90 and 91: in Algorithms 2.15 IntegerToRNS and 2.16 RNSToInteger, the moduli m_i should be pairwise coprime. [reported by Wolfgang Ehrhardt, 15 November 2009] Page 91, line -9: replace "Since M_1 is a multiple of x_i" by "Since M_1 is a multiple of m_i" (idem for the following two occurrences of x_i) Page 91, line -6: replace "X_1 = x_1 mod m_1" by "X_1 = x_i mod m_i" Page 92, Exercise 2.4 should be deleted, since it corresponds to a section from a previous version, which was removed. [reported by Wolfgang Ehrhardt, 15 November 2009] Page 96, line 7: replace "\beta <= |x|" by "\beta^e <= |x|" Page 96, line 9: replace "." by ";" after "in the IEEE 754 standard" [reported by Wolfgang Ehrhardt, 28 December 2009] Page 97, line -8: add "for beta=2" after "values up to about 10^646456993" [reported by Wolfgang Ehrhardt, 28 December 2009] Page 98, line -2: replace "in rounded to nearest mode" by "in rounding ..." Page 99, line 1: replace "<>" by "!=" Page 99, line 9: replace "integer multiples" by "positive integer multiples" and the Greek letter "eta" by "+-eta" Page 100, line 7: "nor the largest normal number": add "in absolute value" Page 100, lines 19-20: replace "normal floating-point numbers" by "normal positive floating-point numbers" Page 104, Theorem 3.1.1: replace "a binary floating-point system" by "a floating-point system" Page 105, line 18: replace "remember that IEEE 754 only considers radix 2" by "for radix 2" Page 105, lines -16 and following: "rho" should read "beta" [reported by Wolfgang Ehrhardt, 15 November 2009] Page 105, line -10: replace "0.1 b_1...b_n b_{n+1}" by "0.1 b_2...b_n b_{n+1}" Page 106, Algorithm RoundingPossible: - replace "|y-x| < \epsilon" by "|y-x| <= \epsilon" - replace step 2 by "if o is to nearest then r <- 1 else r <- 0" - replace step 3 by "if y_{n+1} = r and y_{n+2} = ... = y_k = 0 then s <- 0 else s <- 1" - replace step 4 by "if s=1 then return true else return false" - remove step 5 Page 109, Algorithm 3.2, Step 6: remove "e <- 0", since e was already initialized in Step 3. [reported by Wolfgang Ehrhardt, 15 November 2009] Page 110, line -3: replace ";" by "," Page 111, Sterbenz's Theorem: add "if there is no underflow" at the end of the theorem statement. [reported by Wolfgang Ehrhardt, 28 December 2009] Page 111, line -4: "must have the same sign, We assume" should read "must have the same sign. We assume" [reported by Wolfgang Ehrhardt, 28 December 2009] Page 113, caption of Figure 3.1: replace "most significand" by "most significant" and "Case (a)," by "Case (a):" Page 114, line before Algorithm 3.4 ShortProduct: replace "FullProduct(A,B,n)" by "FullProduct(A,B)" Page 114, Algorithm 3.4 ShortProduct: n_0 >= 1 is a threshold that should be optimized for the given code base. [reported by Wolfgang Ehrhardt, 15 November 2009] Page 115, just below Figure 3.2: replace "The most significant neglected terms ... C_2 and C_3" by "... C'_2 and C'_3" Page 115, line -7: ShortProduct should appear in boldface Page 115, line -3 to page 116, line 2: replace beta by gamma to avoid confusion with the word base. [reported by Wolfgang Ehrhardt, 15 November 2009] Page 117, line -1: replace "Fig 3.3" by "Fig. 3.3" Page 121, Algorithm 3.5 ApproximateReciprocal, step 11: X_h \beta^h should read X_h \beta^{\ell} [reported by Marco Bodrato, 10 December 2009] Page 125, line -10: replace "just replace \beta" by "just replace \mu" Page 126, lines 6-8, including the displayed equation: replace "\beta" by "\mu" Page 126, line 12: replace "Karatsuba and Toom-Cook range" by "... ranges" Page 127, line -6: replace "S(n-k)" by "D^*(n-k)" Page 129, line 3 of proof: replace "s^2 + r + 1 <= (s+1)^2" by "(s^2 + r + 1) 2^{2k} <= (s+1)^2 2^{2k}" Page 129, line -4: replace "x^{n/2}-1" by "\beta^{n/2}-1" Page 132, line 9: "A(X_h^2)" should read "A X_h^2" [reported by Wolfgang Ehrhardt, 15 November 2009] Page 132, line 11: replace "gives 1" by "give 1" Page 134, Algorithm 3.11, Step 1: the italic "o" should read as the rounding mode symbol like in the previous line (idem in the second line after Algorithm 3.11). [reported by Wolfgang Ehrhardt, 15 November 2009] Page 138, line -7: "In her PhD" should read "In her PhD thesis" [reported by Wolfgang Ehrhardt, 28 December 2009] Page 139, line 17: replace "for a small numbers" by "for a small number" Page 166, after (4.32): "However, the limit in the definition (4.32)" should read "However, formula (4.32)". [reported by Wolfgang Ehrhardt, 15 November 2009] Page 167, lines 9 and -8: "R(s)" should read as "\Re(s)" as on page 204 Page 177, line -9: "n in N" should be "n in N^*" [reported by Wolfgang Ehrhardt, 28 December 2009] Page 178, line 9: replace "the tangent number" by "the tangent numbers" Page 181, paragraph "Argument Expansion": replace 'k' by '\ell' to avoid confusion with the modulus 'k' [reported by Wolfgang Ehrhardt, 28 December 2009] Page 183, line 7: replace "(4.76) and (4.77)" by "(4.75) and (4.76)" [reported by Wolfgang Ehrhardt, 28 December 2009] Page 184: the "Constants" paragraph is not up-to-date with Table 4.1 page 185, and should be removed. Page 186, line -7, last displayed equation: a factor '2^k' is missing inside the summation Page 194, line 3: replace "1" by "j=1" under the summation sign [reported by Wolfgang Ehrhardt, 28 December 2009] Page 196, Exercise 4.22, line 2, $z \in C$ should be $z \in \C$ Page 199, Exercise 4.41: "exp(A(x)" should read "exp(A(x))", and a dot (.) is missing at the end of the displayed formula in item (b). Page 201, line 3: replace "et al" by "et al.", and move the sentence "A more recent book ..." one sentence earlier. Page 201, line 20: replace "4.19" by "(4.19)" Page 202, line 15: a space is missing between "\S9.12" and "\S19.28" Page 207, line -3 and -2: remove "since 1993" [reported by Wolfgang Schmid, 11 December 2009] Page 208, line 4: "gmplib.org" should read "http://gmplib.org" Page 208, lines 15 and 16: "Toom-Cook 3,2 and Toom-Cook 4,2" should read "Toom-Cook-(3,2) and Toom-Cook-(4,2)" [reported by Wolfgang Ehrhardt, 15 November 2009] Page 224, reference [148]: "Birkhauser" should have an umlaut over the "a" [reported by Wolfgang Ehrhardt, 15 November 2009] Page 236, left column, line 13: "Sidimohamed" should read "Sidi Mohamed" [reported by Sidi Mohamed Sedjelmaci, 12 November 2009] Version 0.5 (21 February 2010, xvi+245 pages): ============================================= Page 23, line 3 of Figure caption: "Ghz" should read "GHz" [reported by Wolfgang Ehrhardt, 21 February 2010] Page 24, Algorithm 1.10: add the input condition gcd(b_0,\beta)=1 [reported by Wolfgang Ehrhardt, 26 February 2010] Page 41, Algorithm 1.24: add the input condition A > 0 [reported by Wolfgang Ehrhardt, 26 February 2010] Page 43, Exercise 1.4: "Khatchtrian" should read "Khachatrian" [reported by Wolfgang Ehrhardt, 21 February 2010] Page 44, line -5: "Burgisser" should have an umlaut over the "u" [reported by Wolfgang Ehrhardt, 21 February 2010] Page 64, line -8: replace "n=6" by "\beta=64" [reported by Wolfgang Ehrhardt, 26 February 2010] Page 67, Algorithm 2.7: replace "multiplication" by "reduction" in the header [reported by Wolfgang Ehrhardt, 26 February 2010] Page 76, line 3 of Algorithm 2.12: replace "=" by "from" and similarly in Algorithms 2.13, 2.14, 4.4 Page 79, Algorithm 2.15: replace the input condition "k >= 2" by "k >= 1", replace "if k = 2" by "if k <= 2" in step 1, and replace step 2 by "return x_1 = x mod m_1, ..., x_k = x mod m_k" [reported by Wolfgang Ehrhardt, 26 February 2010] Page 89, line -14: replace the dot by a comma after "in other words" [reported by Wolfgang Ehrhardt, 28 February 2010] Page 205, line 10: "Steven" should read "Stephen" Page 205, line 15: "/)." should read "/." Page 227, entry [218]: "Andrei N. Toom" should read "Andrei L. Toom" Page 238, line 8 (left): "Maze, G\'erald" should read "Maze, G\'erard" Page 239, in "Papanikolaou,Thomas" insert a space after the comma [reported by Wolfgang Ehrhardt, 28 February 2010] Page 243, line 2 (left): "Toom, Andrei N." should read "Toom, Andrei L." Page 243, line 13 (right): "Steven" should read "Stephen" Version 0.5.1 (5 March 2010, xvi+247 pages, 12pt arXiv version): =============================================================== Page 10, Algorithm OddEvenKaratsuba, remove the line "k <- ceil(m/2), \ell <- ceil(n/2)" (these value are not used). [reported by Naveen Nathan, 5 May 2010] Page 41, line -2: "Fast conversions" should read "Fast conversion" [reported by Anne Rix, 16 June 2010] Page 48, 5th paragraph: a space is missing between "Toom" and "[218]" Page 92, line 3 of Definition 3.1.1: a space is missing in "rounding of" [reported by Anne Rix, 16 June 2010] Page 110, last line: "multiplications" should read "multiplication" [reported by Anne Rix, 16 June 2010] Page 145, line 8: "Sometime" should read "Sometimes" Page 178, line 3 of Sec. 4.9: "4.8.4)" should read "4.8.4" [reported by Anne Rix, 16 June 2010] Page 198, line -4: "(4.5)" should read "(section 4.5)" [reported by Anne Rix, 16 June 2010] Page 228, reference [230]: "Eigevalue" should read "Eigenvalue" Page 244, "Vuillemin, Jean Etienne" should read "Vuillemin, Jean \'Etienne" Version 0.5.1 (5 March 2010, xvi+227 pages, CUP style): ====================================================== Page 9, Algorithm OddEvenKaratsuba, remove the line "k <- ceil(m/2), \ell <- ceil(n/2)" (these values are not used). [reported by Naveen Nathan, 5 May 2010] Page 38, 1st line of Sec. 1.7.2, "Fast conversions routines" should read "Fast conversion routines" [reported by Anne Rix, 16 June 2010] Page 44, line -10: a space is missing between "Toom" and "[218]" Page 87, line 3 of Definition 3.1.1: a space is missing in "rounding of" [reported by Anne Rix, 16 June 2010] Page 104, line 9 of Sec. 3.4: "multiplications" should read "multiplication" [reported by Anne Rix, 16 June 2010] Page 136, line 1: "Sometime" should read "Sometimes" Page 166, line 3 of Sec. 4.9: "4.8.4)" should read "4.8.4" [reported by Anne Rix, 16 June 2010] Page 186, line 5: "(4.5)" should read "(section 4.5)" [reported by Anne Rix, 16 June 2010] Bibliography: in references [68], [81], [84], [107], [121], [140], [143], [177], [226], [228], "second edn." should read "Second edn.", "third edn." should read "Third edn.", etc [some of these reported by Anne Rix, 16 June 2010] Page 208, reference [230]: "Eigevalue" should read "Eigenvalue" Page 224, "Vuillemin, Jean Etienne" should read "Vuillemin, Jean \'Etienne" Version 0.5.2 (31 July 2010, xvi+247 pages, 12pt version): ========================================================= None so far. Version 0.5.3 (1 August 2010, xvi+223 pages, CUP style): ======================================================= None. Version 0.5.5 (8 September 2010, xvi+223 pages, CUP style): ========================================================== None. [See file CUP-errata.txt for further errata on Version 0.5.7 and later, and on the version printed by Cambridge University Press, November 2010.]