这是我最近一次采访中问的一个问题,我想知道(我实际上不记得数值分析的理论,所以请帮助我:)
如果我们有一些函数,它会累积浮点数:
std::accumulate(v.begin(), v.end(), 0.0);
v
是std::vector<float>
,例如。我怀疑将数字按升序排序会实际上使数字错误减少,但是很遗憾,我自己无法证明这一点。
附言我确实意识到这可能与现实世界的编程无关,只是感到好奇。
最佳答案
您的直觉基本上是正确的,按升序排列(数量级)通常可以使事情有所改善。考虑以下情况:我们要添加单精度(32位)浮点数,并且有10亿个值等于1/(10亿),而一个值等于1。如果先出现1,那么总和就到了到1,因为1 +(1/10亿)由于精度损失而为1。每次添加对总数完全没有影响。
如果较小的值排在第一位,那么它们至少会求和,尽管即使如此,我也有2 ^ 30个,而在2 ^ 25个左右之后,我又回到了每个值都不影响总数的情况还有。所以我仍然需要更多技巧。
这是一个极端的情况,但是总的来说,相加幅度相似的两个值要比相差幅度较大的两个值更准确,因为以这种方式“舍弃”了较少的精度位。通过对数字进行排序,可以将大小相似的值组合在一起,并按升序将它们相加,从而为较小的值提供累积达到较大数字的大小的“机会”。
但是,如果涉及负数,则很容易“胜过”这种方法。考虑三个值求和,{1, -1, 1 billionth}
。算术上正确的总和是1 billionth
,但是如果我的第一个加法涉及很小的值,那么我的最终总和将为0。在6个可能的阶数中,只有2个是“正确的”-{1, -1, 1 billionth}
和{-1, 1, 1 billionth}
。所有6个阶次给出的结果在输入中的最大幅度值的刻度上(0.0000001%输出)都是准确的,但是对于其中4个阶次,结果在真实解的刻度上(100%输出)是不准确的。您要解决的特定问题将告诉您前者是否足够好。
实际上,您可以玩的技巧更多,而不仅仅是按排序顺序添加它们。如果您有很多非常小的值,中等数量的中间值和少量大值,那么首先将所有较小的值相加,然后分别将中间值相加,再将这两个总数相加,可能是最准确的方法一起添加大的找到浮点加法的最准确组合并不是一件容易的事,但是要应对非常糟糕的情况,您可以将整个运行总计保持在不同的幅度,将每个新值添加到最匹配其幅度的总和,当运行的总计开始变得太大而无法达到其幅度时,请将其添加到下一个总计中,然后开始一个新的总计。从逻辑上讲,此过程等效于以任意精度类型执行总和(因此您可以这样做)。但是考虑到按升序或降序数量级的简单选择,升序是更好的选择。
它确实与真实世界的编程有关,因为在某些情况下,如果您不小心砍掉了由大量值组成的“沉重”尾部,那么每个尾部都太小而无法单独影响,则计算可能会变得非常错误。总和,或者如果您放弃了许多单独影响总和的最后几位的小值而导致的精度过高。如果尾部可以忽略不计,那么您可能不在乎。例如,如果您只将少量的值加在一起,而只使用了一些重要的和。
关于c++ - 应该以哪种顺序添加浮点数以获得最精确的结果?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/6699066/