Errata for the book "Modern Computer Arithmetic" (the printed version, and electronic versions from 17 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 printed by Cambridge University Press (November 2010) and ================================================================= Version 0.5.7 (17 September 2010, xvi+223 pages, CUP style): =========================================================== Page 19, line -5: "the dividend A is at most twice as large as the divisor B" should read "the dividend A has at most twice as many words as the divisor B" and just after, "When A is more than twice as large as B" should read "When A has more than 2n words" [reported by Warren Ferguson in his SIAM review of the book] Page 42, Exercise 1.25: "special base" should read "special case". Page 186, line 4: http://gmplib.org should read http://gmplib.org/ Page 187, line 12: http://www.mpfr.org should read http://www.mpfr.org/ (idem page 190, line 5) Page 188, line -10: http://www.maplesoft.com should read http://www.maplesoft.com/ [reported by Torbjorn Granlund, 2 November 2010] Version 0.5.9 (7 October 2010, xvi+223 pages, CUP style): ========================================================== In the whole book, the spacing after "i.e." may be too large, for example on page 50, line -2. In some places it is correct, for example page 11, line -3. Idem with "e.g." (for example, page 46, line -8) and "etc." (for example, page 146, line 9). [reported by Jeremie Detrey, 15 December 2010] Page 7, Algorithm 1.4, line 2: remove the dot at the end of the line. [reported by Gaetan Bisson, 15 December 2010] Page 17, Algorithm 1.7, line 9: "q_j \beta^j" should read "q_j \beta^{j-1}" [reported by Peter Dixon, 12 February 2015] Page 17, Algorithm 1.7: in some rare cases, we can have A larger or equal to \beta^{n+j} after step 8, which would break the next iteration. [reported by Niels Möller, 18 November 2018] The fix is to replace step 4 by: "q_j = min (\beta - 1, floor(A / \beta^{n+j}))" Proof: we prove the loop invariant A < \beta^j B' at step 4: at the beginning this is true since A < \beta^{m+n} <= \beta^{m-1} B', and afterwards this remains true since: (1) either q_j = floor(A / \beta^{n+j}), and A >= 0 at step 6, in which case A < \beta^{n+j} since the subtraction at step 5 kills the coefficient q_j; (2) either q_j = \beta - 1, and A >= 0 at step 6, in which case A - q_j \beta^{j-1} B' < \beta^j B' - (\beta-1) \beta^{j-1} B' = \beta^{j-1} B'; (3) or A < 0 at step 6, we then have A < \beta^{j-1} B' after step 8, thus A < \beta^j B' at the next iteration. Remark: an alternate version would be to take for B' the largest multiple of B less than \beta^{n+1}. Then the subtraction at step 5 cannot yield A < 0, but in some rare cases we might still have A >= \beta^{n+j} after the subtraction at step 5. In that case subtracting again \beta^{j-1} B' (and increasing q_j) should ensure A < \beta^{n+j}. Page 19, line 10: "A mod \beta_{2k}" should read "A mod \beta^{2k}" [reported by Wolfgang Ehrhardt, 13 January 2011] Page 22, Algorithm 1.10: add the input condition "n > 2" otherwise k is undefined at step 5 [reported by Wolfgang Ehrhardt, 13 January 2011] Page 40, Exercise 1.4: replace the index "j" by "i" in the definition of B Page 50, last sentence of Section 2.2: the use of "--" and "," is inconsistent, replace ", say at least ten words" by " -- say at least ten words" [reported by Jeremie Detrey, 15 December 2010] Page 57, the complexity analysis of Algorithm 2.4 (FFTMulMod) is incorrect. A correct analysis can be found at https://members.loria.fr/PZimmermann/mca/fft.pdf [reported by Emmanuel Thomé, 17 January 2018] Page 60, in step 3 of the Montgomery-Svoboda algorithm, the final result R might still be larger than \beta^n after one subtraction (consider for example \beta=4, n=2, C=255, N=13). Thus a second subtraction might be needed, for example replace step 5 of Algorithm 2.6 by "while R >= \beta^n do R = R - N; return R" [reported by Cyril Bouvier, 29 February 2012] Page 87, line -11, remove an extra space after "stochastic rounding" [reported by Jeremie Detrey, 15 December 2010] Page 112, line -3: \beta^{-h} should be 2\beta^{-h} in the induction hypothesis. Page 116, Algorithm 3.10, lines 6 and 7: remove the dots at the end of the lines (before the comment on line 6). Page 117, the proof of the bound P >= 1 + p*log(b)/log(B) is incomplete. [reported by Vincent Lefèvre, 1st September 2012] Indeed, if x = b^{e-1}, and X < x, we should have |x-X| < ulp(x)/(2b) instead of |x-X| < ulp(x)/2 to guarantee that X is rounded to x to nearest. This corner case is covered by the same bound as follows (add the factor 1/2 for rounding to nearest): "If x = b^{e-1} and X < x we should have ulp(X) < ulp(x)/b, which translates into B^{E-P} < b^{e-p-1}. But if X < x, we also have B^{E-1} <= b^{e-1}, which gives B^{E-P} <= b^{e-1} B^{1-P}, and it thus suffices to have b^{e-1} B^{1-P} <= b^{e-p-1}, which gives the same condition as in the non-corner cases." Also the sentence "Since |x| < b^e, and X is the rounding of x, it suffices to have B^{E-1} <= b^e" is not clear. It should be replaced by the following paragraph: "Without loss of generality we can assume B^{E-1} <= b^e. Indeed, if that does not hold, we have: b^{e-1} <= x < b^e < B^{E-1} <= X < B^E then since B^{E-1} is representable in radix B necessarily we have X = B^{E-1}. Now |X-x| > b^{e-p} [since x <= b^e (1 - b^(-p))] > b^e B^{1-P} [assume P >= 1 + p*(log b)/log(B)] > B^{E-2} B^{1-P} [since b^e > B^{E-2}] = B^{E-1-P} thus X rounded to nearest cannot equal x." Page 122, line 8: "complex FFT" should read "the complex FFT". Page 129, line 16: "Exercise3.15" should read "Exercise 3.15". Page 148, line -14: the comma in "For j < x^2," should not be in math mode, and there is too much space after it. [reported by Gaetan Bisson, 15 December 2010] Page 149, line -1: the comma should be in math mode, not in text mode (there are 17 other occurrences of this in Chapter 4, when a comma follows a displayed fraction) [reported by Jeremie Detrey, 15 December 2010] Page 155, Equation (4.59): the equation is valid only for k > 0; for k=0 the correct value is C_0 = 1. [reported by Siegfried Rump, 01 December 2017] Page 157, line 3: "Tangent numbers" should read "tangent numbers" for consistency with say page 155, line -1 (idem page 177, line 7). Similarly "Secant numbers" should read "secant numbers" on page 176 line -10, and page 177 line 4. [reported by Jeremie Detrey, 15 December 2010] Page 163, line 14 of Section 4.8.5, replace "the square root with positive real part" by "the square root with $b_{j+1}$ closest to $a_{j+1}$" (see for example The arithmetic-geometric mean of Gauss, David A. Cox, 1984). Page 175, Exercise 4.27 (also page 179, line 1): for consistency, "Remark" should be in small caps (as on page 24). Page 177, Exercise 4.41: in the time bound, change the exponent of (log n) from 2+epsilon to 3+epsilon. [The original time bound in the exercise is achievable, but not by the method indicated.] Page 181, line 25, replace "the one with positive real part" by "the one with $b_{j+1}$ closest to $a_{j+1}$" Page 182, lines 12-13: the formula for the complex square root is incorrect if x is negative. A correct formula can be deduced from the formula for positive x by multiplying both sides by i = sqrt(-1). [reported by Judy-anne Osborn, 14 March 2013] Page 199, reference [138], "Workshop Selected" should read "Workshop on Selected".