Errata of book "Modern Computer Arithmetic". Note: an error in version n might have be present in previous versions. We only mention it in the more 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 (March 2009, 215 pages): ===================================== Pages 13 and 14 were left blank Version 0.3 (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-Schönhage 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 (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 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 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 "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 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 194, line 3: replace "1" by "j=1" under the summation sign [reported by Wolfgang Ehrhardt, 28 December 2009] Page 199, Exercise 4.41: "exp(A(x)" should read "exp(A(x))" Page 207, line -3 and -2: remove "since 1993" [reported by Wolfgang Schmid, 11 December 2009] 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]