Algorithm 908
Algorithm 908: Online Exact Summation of Floating-Point Streams. 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 for this software
References in zbMATH (referenced in 6 articles )
Showing results 1 to 6 of 6.
Sorted by year (- Lange, Marko; Oishi, Shin’ichi: A note on Dekker’s FastTwoSum algorithm (2020)
- Langrené, Nicolas; Warin, Xavier: Fast and stable multivariate kernel density estimation by fast sum updating (2019)
- Beebe, Nelson H. F.: The mathematical-function computation handbook. Programming using the MathCW portable software library (2017)
- Flocke, N.: Algorithm 954: An accurate and efficient cubic and quartic equation solver for physical applications (2015)
- Graillat, Stef; Lauter, Christoph; Tang, Ping Tak Peter; Yamanaka, Naoya; Oishi, Shin’ichi: Efficient calculations of faithfully rounded (l_2)-norms of (n)-vectors (2015)
- Zhu, Yong-Kang; Hayes, Wayne B.: Algorithm 908: Online exact summation of floating-point streams (2010)