Correct Rounding and a Hybrid Approach to Exact Floating-Point Summation
Correct Rounding and a Hybrid Approach to Exact Floating-Point Summation
复制标题
正确的舍入和精确浮点求和的混合方法
DOI：
--
复制
发表时间：
2009
影响因子：
3.1
通讯作者：
W. Hayes
中科院分区：
文献类型：
--
作者：
Yong;W. Hayes
我们提出了两个算法计算正确的舍入和数组的浮点数。首先，iFastSum改进了我们以前的FastSum，它不需要原始数组之外的额外空间，原始数组被销毁。在一般情况下，它的运行速度比FastSum快20%，在使用极端病态数据时快两倍。第二种算法是HybridSum，它将三种求和思想结合在一起：分割尾数、基数排序和使用iFastSum。结果是，当被加数大于10^4时，对于给定的n，它的运行时间几乎是一个常数，与条件数无关。在一般情况下，它的运行速度几乎与iFastSum一样快，在使用病态数据时，它的运行速度比iFastSum快得多。HybridSum只需要一次通过输入数组，并使用常量存储，因此它适合作为“在线”算法进行精确求和。这两种算法都不需要额外的精度，并且都可以在任何基础上工作。它们的精度是保证独立的条件数和被加数。
We present two algorithms for computing correctly rounded sums of arrays of floating-point numbers. First, iFastSum improves upon our previous FastSum by requiring no additional space beyond the original array, which is destroyed. It runs about 20% faster than FastSum in the general case and two times faster when extremely ill-conditioned data are used. The second algorithm is HybridSum, which combines three summation ideas together: splitting the mantissa, radix sorting, and using iFastSum. The result is that when the number of summands is greater than about $10^4$, for a given $n$ its running time is almost a constant, independent of the condition number. It runs almost as fast as iFastSum in the general case and much faster than iFastSum when ill-conditioned data are used. HybridSum requires only one pass through the input array and uses constant storage, and it is thus suitable for exact summation as an “online” algorithm. Neither algorithm requires extra precision accumulators, and both work in any base. Their accuracy is guaranteed independent of the condition number and the number of summands.