A New Distillation Algorithm for Floating-Point Summation

Abstract : The summation of n floating-point numbers is ubiquitous in numerical computations. We present a new distillation algorithm for floating-point summation which is stable, efficient, and accurate. The algorithm iteratively “distills” the summands without discarding any significant digit until the partial sums cannot change the whole sum. It uses standard floating-point arithmetic and does not rely on the choice of radix or any other specific assumption. Furthermore, the error bound of our algorithm is independent of n and less than 1 ulp.