Summary: Given a multiset \(X= \{x_1,\dots, x_n\}\) of real numbers, the floating-point set summation (FPS) problem asks for \(S_n= x_1+\cdots+ x_n\), and the floating point prefix set summation problem (FPPS) asks for \(S_k= x_1+\cdots+ x_k\) for all \(k=1,\dots, n\). Let \(E^*_k\) denote the minimum worst-case error over all possible orderings of evaluating \(S_k\). We prove that if \(X\) has both positive and negative numbers, it is NP-hard to compute \(S_n\) with the worst-case error equal to \(E^*_n\). We then give the first known polynomial-time approximation algorithm for computing \(S_n\) that has a provably small error for arbitrary \(X\). Our algorithm incurs a worst-case error at most \(2(\lceil\log(n- 1)\rceil+ 1)E^*_n\). After \(X\) is sorted, it runs in \(O(n)\) time, yielding an \(O(n^2)\)-time approximation algorithm for computing \(S_k\) for all \(k= 1,\dots, n\) such that the worst-case error for each \(S_k\) is less than \(2(\lceil\log(k- 1)\rceil+ 1)E^*_k\).
For the case where \(X\) is either all positive or all negative, we give another approximation algorithm for computing \(S_n\) with a worst-case error at most \(\lceil\log\log n\rceil E^*_n\). Even for unsorted \(X\), this algorithm runs in \(O(n)\) time. Previously, the best linear-time approximation algorithm had a worst-case error at most \(\lceil\log n\rceil E^*_n\), while \(E^*_n\) was known to be attainable in \(O(n\log n)\) time using Huffman coding. Consequently, FPPS is solvable in \(O(n^2)\) time such that the worst-case error for each \(S_k\) is the minimum. To improve this quadratic time bound in practice, we design two on-line algorithms that calculate the next \(S_k\) by taking advantage of the current \(S_k\) and thus reduce redundant computation.
For the entire collection see [Zbl 0893.00039].