On accurate floating-point summation

ABSTRACT

cumulation of floating-point sums is considered on a computer which performs t-digit base &bgr; floating-point addition with exponents in the range —m to M. An algorithm is given for accurately summing n t-digit floating-point numbers. Each of these n numbers is split into q parts, forming q·n t-digit floating-point numbers. Each of these is then added to the appropriate one of &eegr; auxiliary t-digit accumulators. Finally, the accumulators are added together to yield the computed sum. In all, q·n + &eegr; - 1 t-digit floating-point additions are performed. Let &ngr; = ⌈(M + m + 1)/(&eegr; + 1)⌉. If n ≤ (1/q)&bgr;⌈((q-1)/q)t⌈-&ngr;+1 (*), then the relative error in the computed sum is at most ⌈(t + 1)/&ngr;⌉&bgr;1-t. Further, with an additional q + &eegr; - 1 t-digit additions, the computed sum can be corrected to full t-digit accuracy. For example, for the IBM/360 (&bgr; = 16, t = 14, M = 63, m = 64), typical values for q and &eegr; are q = 2 and &eegr; = 32. In this case, (*) becomes n ≤ 1/2 × 164 = 32,768, and we have ⌈(t + 1)/&ngr;⌉&bgr;1-t = 4 × 16-13.

REFERENCES

• 1: James H. Wilkinson, Rounding Errors in Algebraic Processes, Dover Publications, Incorporated, 1994
• 2: Jack M. Wolfe, Reducing truncation errors by programming, Communications of the ACM, v.7 n.6, June 1964 [doi>10.1145/512274.512287]
• 3: Michael A. Malcolm, A description and comparison of subroutines for computing Euclidean inner products on the IBM 360, Stanford University, Stanford, CA, 1970
• 4: Jordan, D.F. ANL F154S-DOTP, extra-precision accumulating inner product. Argonne Nat. Lab., Appl. Math. Div., System/360 Lib. Subroutine, Argonne, Ill., Nov. 1967.
• 5: Moller, Ole. Quasi double-precision in floating point addition, BIT 5 (1965), 37-50.
• 6: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997

INDEX TERMS

Keywords:
error analysis, floating-point summation