Efficient minimization of numerical summation errors

Given a multiset X = {x₁,⋯, x_n} of real numbers, the floating-point set summation (FPS) problem asks for S_n = x₁ + ··· + x_n, and the floating point prefix set summation problem (FPPS) asks for S_k = x₁ + ··· + X_k for all k = 1,⋯, n. Let E^*_k denote the minimum worst-case error over all possible orderings of evaluating Sk-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 worstcase error at most 2([log(n - 1)] + 1)E^*_n.¹ After X is sorted, it runs in O(n) time, yielding an O(n²)-time approximation algorithm for computing S_k for all k = 1,⋯, n such that the worst-case error for each Sk is less than 2[log(k - 1)1 + 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 [log log n]E^*_n. Even for unsorted X, this algorithm runs in 0(n) time. Previously, the best linear-time approximation algorithm had a worst-case error at most flog n] 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²) 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.