algorithm - 有效减少重复操作带来的舍入误差的影响

Question

我最近刚刚遇到了用于最小化舍入的 Kahan（或补偿）求和算法，我想知道是否有用于除法和/或乘法以及减法的等效算法（如果碰巧有，我知道关于关联性）。任何语言、伪代码或链接的实现示例都很棒！

谢谢

Answer 1

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

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

如果您有可用的 FMA（融合乘加），则可以通过以下方式轻松完成：

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

经过这两次操作后，如果没有发生上溢或下溢，p + r则完全等于a * b不进行四舍五入。这也可以在没有 FMA 的情况下完成，但难度更大。如果您对这些算法感兴趣，您可以从下载crlibm 文档开始，其中详细介绍了其中的几个。

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

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

Answer 2

设计数值稳定的算法本身就是一门学科和研究领域。这不是您可以通过“备忘单”有意义地做（或学习）的事情——它需要特定的数学知识，并且需要针对每个特定的算法来完成。如果您想了解如何做到这一点，维基百科文章中的参考资料听起来不错：Nicholas J. Higham，数值算法的准确性和稳定性，工业与应用数学学会，费城，1996 年。ISBN 0-89871-355- 2.

诊断算法稳定性的一种相对简单的方法是使用区间算术。

Answer 3

您可以使用 bignums 和有理分数而不是浮点数，在这种情况下，您仅受内存的有限可用性限制以保持所需的精度。