Ultimately Fast Accurate Summation
Ultimately Fast Accurate Summation
复制标题
DOI：
10.1137/080738490
复制
发表时间：
2009-08
期刊：
影响因子：
--
通讯作者：
S. Rump
中科院分区：
文献类型：
--
作者：
S. Rump
我们提出了两个新算法FastAccSum和FastPrecSum，一个用于计算浮点数和的忠实舍入，另一个用于计算“好像”以K倍精度计算的结果。忠实舍入意味着计算结果要么是精确结果的浮点近邻之一，要么等于精确和（如果这是一个浮点数）。这些算法是基于我们之前的AccSum和PrecSum算法，并将它们提高了25%。第一种算法适应求和的条件数；也就是说，计算时间与问题的难度成正比。第二种算法不需要额外的内存，计算时间仅取决于求和次数和K。这两种算法都是已知的最快的。它们允许良好的指令级并行性，因此它们在测量计算时间方面也很快。该算法只需要在一个工作精度（例如双精度）下进行标准的浮点加法、减法和乘法。
We present two new algorithms FastAccSum and FastPrecSum, one to compute a faithful rounding of the sum of floating-point numbers and the other for a result “as if” computed in $K$-fold precision. Faithful rounding means the computed result either is one of the immediate floating-point neighbors of the exact result or is equal to the exact sum if this is a floating-point number. The algorithms are based on our previous algorithms AccSum and PrecSum and improve them by up to 25%. The first algorithm adapts to the condition number of the sum; i.e., the computing time is proportional to the difficulty of the problem. The second algorithm does not need extra memory, and the computing time depends only on the number of summands and $K$. Both algorithms are the fastest known in terms of flops. They allow good instruction-level parallelism so that they are also fast in terms of measured computing time. The algorithms require only standard floating-point addition, subtraction, and multiplication in one working precision, for example, double precision.