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".