有效减少重复运算带来的舍入误差影响
我最近刚刚遇到了用于最小化舍入的Kahan（或补偿）求和算法，我想知道是否有等效的除法和/或乘法以及减法算法（如果恰好有，我知道结合性）。任何语言、伪代码或链接的实现示例都很棒！
谢谢
I just recently came across the Kahan (or compensated) summation algorithm for minimizing roundoff, and I'd like to know if there are equivalent algorithms for division and/or multiplication, as well as subtraction (if there happens to be one, I know about associativity). Implementation examples in any language, pseudo-code or links would be great!
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您可以使用 bignum 和有理分数而不是浮点数，在这种情况下，您仅受到有限的可用内存来保持所需精度的限制。
You could use bignums and rational fractions rather than floating point numbers in which case you are limited only by the finite availability of memory to hold the require precision.
减法通常通过 Kahan 方法处理。
对于乘法，有一些算法可以将两个浮点数的乘积转换为两个浮点数的和而不进行舍入，此时您可以使用卡汉求和或其他一些方法，具体取决于您接下来需要做什么产品。
如果您有可用的 FMA（融合乘加），则可以轻松完成如下操作：
在这两个操作之后，如果没有发生上溢或下溢，则
p + r完全等于a * b不进行舍入。没有 FMA 也可以实现这一点，但难度更大。如果您对这些算法感兴趣，可以首先下载crlibm文档，其中详细介绍了其中的几个。分裂……好吧，最好避免分裂。除法很慢，补偿除法更慢。您可以做到，但如果没有 FMA，这会非常困难，而有了 FMA 则并非易事。最好设计你的算法来尽可能避免它。
请注意，所有这一切很快就会变成一场失败的战斗。在极少数情况下，这些技巧是有用的——对于任何更复杂的事情，最好使用更宽精度的浮点库，例如 mpfr。除非您是该领域的专家（或想成为该领域的专家），否则通常最好只是学习使用这样的库。
Subtraction is usually handled via the Kahan method.
For multiplication, there are algorithms to convert a product of two floating-point numbers into a sum of two floating-point numbers without rounding, at which point you can use Kahan summation or some other method, depending on what you need to do next with the product.
If you have FMA (fused multiply-add) available, this can easily be accomplished as follows:
After these two operations, if no overflow or underflow occurs,
p + ris exactly equal toa * bwithout rounding. This can also be accomplished without FMA, but it is rather more difficult. If you're interested in these algorithms, you might start by downloading thecrlibmdocumentation, which details several of them.Division... well, division is best avoided. Division is slow, and compensated division is even slower. You can do it, but it's brutally hard without FMA, and non-trivial with it. Better to design your algorithms to avoid it as much as possible.
Note that all of this becomes a losing battle pretty quickly. There's a very narrow band of situations where these tricks are beneficial--for anything more complicated, it's much better to just use a wider-precision floating point library like mpfr. Unless you're an expert in the field (or want to become one), it's usually best to just learn to use such a library.
将算法设计为数值稳定本身就是一门学科和研究领域。这不是你可以通过“备忘单”有意义地做（或学习）的事情——它需要特定的数学知识，并且需要针对每个特定的算法来完成。如果您想了解如何做到这一点，维基百科文章中的参考听起来相当不错：Nicholas J. Higham，数值算法的准确性和稳定性，工业和应用数学学会，费城，1996。ISBN 0-89871-355- 2.
诊断算法稳定性的一个相对简单的方法是使用区间算术< /a>.
Designing algorithms to be numerically stable is an academic discipline and field of research in its own right. It's not something you can do (or learn) meaningfully via "cheat sheets" - it requires specific mathematical knowledge and needs to be done for each specific algorithm. If you want to learn how to do this, the reference in the Wikipedia article sounds pretty good: Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society of Industrial and Applied Mathematics, Philadelphia, 1996. ISBN 0-89871-355-2.
A relatively simple way to diagnose the stability of an algorithm is to use interval arithmetic.