Best “ordering” for floating-point addition

ABSTRACT

This correspondence examines the influence of the summation order on the numerical accuracy of the resulting sum when the addition is performed using floating-point, finite-precision arithmetic. A simple statistical model is used to find the relative performance of various addition procedures. It is shown that phrasing the question in terms of finding a best ordering is overly restrictive since the most natural and accurate procedures for performing the addition utilize the storage of intermediate sums as well as performing orderings.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: James Gregory, A comparison of floating point summation methods, Communications of the ACM, v.15 n.9, p.838, Sept. 1972 [doi>10.1145/361573.361584]
• 3: HARTER, H.L. Ordering Statistics and Their Use in Estimation and Testing, Vols. 1 and 2. Superintendent of Documents, U.S. Government Printing Office. Washington, D.C., 1969.
• 4: W. Kahan, Pracniques: further remarks on reducing truncation errors, Communications of the ACM, v.8 n.1, p.40, Jan. 1965 [doi>10.1145/363707.363723]
• 5: Peter Linz, Accurate floating-point summation, Communications of the ACM, v.13 n.6, p.361-362, June 1970 [doi>10.1145/362384.362498]
• 6: Michael A. Malcolm, On accurate floating-point summation, Communications of the ACM, v.14 n.11, p.731-736, Nov. 1971 [doi>10.1145/362854.362889]
• 7: Nai-Kuan Tsao, On the distributions of significant digits and roundoff errors, Communications of the ACM, v.17 n.5, p.269-271, May 1974 [doi>10.1145/360980.360998]
• 8: James H. Wilkinson, Rounding Errors in Algebraic Processes, Dover Publications, Incorporated, 1994
• 9: Jack M. Wolfe, Reducing truncation errors by programming, Communications of the ACM, v.7 n.6, June 1964 [doi>10.1145/512274.512287]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Computer arithmetic

General Terms:
Algorithms, Performance