Fast and Accurate Floating Point Summation with Application to Computational Geometry
Fast and Accurate Floating Point Summation with Application to Computational Geometry
复制标题
快速准确的浮点求和及其在计算几何中的应用
作者：
J. Demmel;Yozo Hida
我们提出了几种简单的算法，用于使用更宽的累加器精确计算n个浮点数的和。设f和F分别为被加数和累加器中的有效位数。那么，在假定渐进下溢、无溢出以及舍入到最近值的算术运算的情况下，通过仅按照指数递减的顺序对各项求和，最多可以精确地累加⌊2F−f/(1−2−f)⌋ + 1个数，得到的和在最后一位大约精确到1.5个单位以内。特别地，如果和为零，则能精确计算出来。我们将此结果应用于IEEE浮点标准中的浮点格式，并研究其性能。我们的结果表明，在没有大量抵消（最常见的情况）时，保证精度的成本比直接求和大约高30 - 40%。如果确实发生大量抵消，计算精确和的成本大约是十倍。最后，我们将我们的算法应用于计算一个鲁棒的几何谓词（用于计算几何），在这种情况下，我们的精确求和算法在一组近乎共面的点上使现有算法提高了两倍。
We present several simple algorithms for accurately computing the sum of n floating point numbers using a wider accumulator. Let f and F be the number of significant bits in the summands and the accumulator, respectively. Then assuming gradual underflow, no overflow, and round-to-nearest arithmetic, up to ⌊2F−f/(1−2−f)⌋+1 numbers can be accurately added by just summing the terms in decreasing order of exponents, yielding a sum correct to within about 1.5 units in the last place. In particular, if the sum is zero, it is computed exactly. We apply this result to the floating point formats in the IEEE floating point standard, and investigate its performance. Our results show that in the absence of massive cancellation (the most common case) the cost of guaranteed accuracy is about 30–40% more than the straightforward summation. If massive cancellation does occur, the cost of computing the accurate sum is about a factor of ten. Finally, we apply our algorithm in computing a robust geometric predicate (used in computational geometry), where our accurate summation algorithm improves the existing algorithm by a factor of two on a nearly coplanar set of points.