# 4.6 Summation Summary

 Java Number Cruncher: The Java Programmer's Guide to Numerical Computing By Ronald  Mak Table of Contents Chapter  4.   Summing Lists of Numbers

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.

 Top

 Java Number Cruncher: The Java Programmer's Guide to Numerical Computing By Ronald  Mak Table of Contents Chapter  4.   Summing Lists of Numbers

References

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.

 Top

 Java Number Cruncher: The Java Programmer's Guide to Numerical Computing By Ronald  Mak Table of Contents Part  II.   Iterative Computations

## Chapter 5. Finding Roots

"Solve for x " is typically what we're asked to do when given an equation involving x as the unknown. One way to do it is to rewrite the equation into the form f ( x ) = 0, and then find the roots, or the zeros, of the function. In other words, we want to find the values of x such that f ( x ) = 0. Depending on the function, there may be more than one root, and they can be either real or complex, or there may be no roots at all. If we draw a graph of f ( x ) in the xy plane, then the real roots are those values of x wherever the plot crosses the x axis. This chapter explores various algorithms for finding real roots that are suitable for a computer.

Traditionally, these algorithms are called methods , as in bisection method and Newton's method. However, to avoid confusion with the methods of Java classes, we'll use the word algorithm instead.

 Top