4.6 Summation Summary

We can sum up, so to speak, the lessons of this chapter:

• When summing lists of numbers with the same sign, add them in the sorted order of the smallest magnitude to the largest.

• Avoid magnitude errors that occur whenever the differences between the binary exponents of the addends exceed 24 for float and 53 for double. The Kahan Summation Algorithm works well despite magnitude errors.

• When summing lists of numbers with mixed signs, avoid cancellation errors by subtotaling the positive and negative numbers separately.

• Double-precision arithmetic is not a cure-all.

• Sometimes we may have to try several summation algorithms before we find one that works.

• The best strategy of all is to gain some insight into the nature of the problem.

Forsythe, George, Michael A. Malcolm, and Cleve B. Moler, Computer Methods for Mathematical Computations , Englewood Cliffs, NJ: Prentice-Hall, 1977.
This book describes the computation of e ^x using the Taylor series in Section 2.3.

Goldberg, David, "What Every Computer Scientist Should Know about Floating-Point Arithmetic," in ACM Computing Surveys , Volume 23, Number 1, March 1991.

Higham, Nicolas J., Accuracy and Stability of Numerical Algorithms , Philadelphia: Society for Industrial and Applied Mathematics, 1996.

Kahan, W., Implementation of Algorithms, Part I , Technical Report 20, lecture notes by W.S. Haugeland and D. Hough, Department of Computer Science, University of California, Berkeley, 1973.
Goldberg, Higham, and Kahan describe the Kahan Summation Algorithm. Goldberg contains a detailed analysis and proof of the method. Higham also analyzes the method and describes the even more ingenious doubly compensated summation ; his Chapter 4 is entirely on summation.

Monahan, John F., Numerical Methods of Statistics , Cambridge, UK: Cambridge University Press, 2001.
This text discusses cancellation errors while computing a sample variance in Section 2.5.