algorithm - 有效降低重复运算带来的舍入误差的影响

Question

我最近刚遇到 Kahan (or compensated) summation algorithm for minimizing roundoff ，我想知道除法和/或乘法以及减法是否有等效的算法(如果恰好有一个，我知道结合性)。任何语言、伪代码或链接的实现示例都很棒!

谢谢

Answer 1

减法通常通过 Kahan 方法处理。

对于乘法，有一些算法可以将两个 float 的乘积转换为两个 float 的和而不进行舍入，此时您可以使用卡汉求和或其他一些方法，具体取决于您的需要接下来对产品进行操作。

如果您有可用的 FMA(融合乘加)，可以按如下方式轻松完成:

p = a*b;
r = fma(a,b,-p);

经过这两次运算，如果没有发生上溢或下溢，则p + r 正好等于a * b，无需四舍五入。这也可以在没有 FMA 的情况下完成，但比较困难。如果您对这些算法感兴趣，可以先下载 crlibm documentation ，其中详细介绍了其中的几个。

除法...好吧，最好避免除法。除法慢，补偿法除法更慢。你可以做到，但没有 FMA 会非常困难，而且有它也很重要。最好设计您的算法以尽可能避免它。

请注意，所有这一切很快就会变成一场失败的战斗。这些技巧在非常有限的情况下是有益的——对于任何更复杂的事情，最好只使用更宽精度的浮点库，如 mpfr。 .除非您是该领域的专家(或想成为该领域的专家)，否则通常最好只学习使用这样的库。