Algorithm 908
Authors:
Open Access
- 1 September 2010
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 37 (3) , 1-13
Abstract
We present a novel, online algorithm for exact summation of a stream of floating-point numbers. By “online” we mean that the algorithm needs to see only one input at a time, and can take an arbitrary length input stream of such inputs while requiring only constant memory. By “exact” we mean that the sum of the internal array of our algorithm is exactly equal to the sum of all the inputs, and the returned result is the correctly-rounded sum. The proof of correctness is valid for all inputs (including nonnormalized numbers but modulo intermediate overflow), and is independent of the number of summands or the condition number of the sum. The algorithm asymptotically needs only 5 FLOPs per summand, and due to instruction-level parallelism runs only about 2--3 times slower than the obvious, fast-but-dumb “ordinary recursive summation” loop when the number of summands is greater than 10,000. Thus, to our knowledge, it is the fastest, most accurate, and most memory efficient among known algorithms. Indeed, it is difficult to see how a faster algorithm or one requiring significantly fewer FLOPs could exist without hardware improvements. An application for a large number of summands is provided.Keywords
This publication has 19 references indexed in Scilit:
- A survey of shadowing methods for numerical solutions of ordinary differential equationsApplied Numerical Mathematics, 2005
- Accurate and Efficient Floating Point SummationSIAM Journal on Scientific Computing, 2004
- Accuracy and Stability of Numerical Algorithms2002
- A Distillation Algorithm for Floating-Point SummationSIAM Journal on Scientific Computing, 1999
- A parallel tree codeNew Astronomy, 1996
- The Accuracy of Floating Point SummationSIAM Journal on Scientific Computing, 1993
- Error analysis of a tree codeThe Astrophysical Journal Supplement Series, 1989
- A hierarchical O(N log N) force-calculation algorithmNature, 1986
- LSODE and LSODI, two new initial value ordinary differential equation solversACM SIGNUM Newsletter, 1980
- A floating-point technique for extending the available precisionNumerische Mathematik, 1971