Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors

Ming-Yang Kao, Jie Wang

Given a multiset $X=\{x_1,...,x_n\}$ of real numbers, the {\it floating-point set summation} problem asks for $S_n=x_1+...+x_n$. Let $E_n^{\ast }$ denote the minimum worst-case error ov…