给定一个递增的有限正数序列。以下两种算法中哪一种更适合计算数字的总和?
s=0;
for \ i=1:n
s=s + z_{i} ;
end
或者:
s=0;
for \ i=1:n
s=s + z_{n-i+1} ;
end
在我看来,最好从最大的数字开始添加到最小的数字,因为误差会越来越小。我们也知道,当我们把一个非常大的数加到一个非常小的数上时,近似的结果可以是大数。
这个对吗?还能说什么呢?
给定一个递增的有限正数序列。以下两种算法中哪一种更适合计算数字的总和?
s=0;
for \ i=1:n
s=s + z_{i} ;
end
或者:
s=0;
for \ i=1:n
s=s + z_{n-i+1} ;
end
在我看来,最好从最大的数字开始添加到最小的数字,因为误差会越来越小。我们也知道,当我们把一个非常大的数加到一个非常小的数上时,近似的结果可以是大数。
这个对吗?还能说什么呢?
这些是整数还是浮点数?假设它是浮点数,我会选择第一个选项。最好将较小的数字相加,然后再将较大的数字相加。使用第二个选项,随着i的增加,您最终会将一个小数添加到一个大数中,这可能会导致问题。这是关于浮点运算的一个很好的资源:每个计算机科学家都应该知道的关于浮点运算的知识
Animal_magic 的答案是正确的,你应该从最小到最大添加数字,但是我想举一个例子来说明原因。
假设我们正在使用浮点格式,这给了我们惊人的 3 位精度。现在我们要添加十个数字:
[1000, 1, 1, 1, 1, 1, 1, 1, 1, 1]
当然,确切的答案是 1009,但我们无法以 3 位格式得到它。四舍五入到 3 位,我们得到的最准确的答案是 1010。如果我们将最小到最大相加,在每个循环中我们得到:
Loop Index s
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 1009 -> 1010
所以我们得到了我们格式的最准确的答案。现在让我们假设我们从最大到最小添加。
Loop Index s
1 1000
2 1001 -> 1000
3 1001 -> 1000
4 1001 -> 1000
5 1001 -> 1000
6 1001 -> 1000
7 1001 -> 1000
8 1001 -> 1000
9 1001 -> 1000
10 1001 -> 1000
由于浮点数在每次运算后都会四舍五入,因此所有加法都被舍入,从而将我们的误差从精确值从 1 增加到 9。现在想象一下,如果要添加的一组数字有 1000,然后是一百个 1,或者一百万。请注意,要真正准确,您需要将最小的两个数字相加,然后将结果放入您的数字集中。
添加任意浮点数通常会产生一些舍入误差,舍入误差与结果的大小成正比。如果您计算单个总和并首先添加最大的数字,则平均结果会更大。所以你会从最小的数字开始添加。
但是如果你产生四个和,你会得到更好的结果(它运行得更快),例如:从 sum1、sum2、sum3、sum4 开始,依次将四个数组元素添加到 sum1、sum2、sum3、sum4。由于每个结果平均仅为原始总和的 1/4,因此您的误差小四倍。
更好的是:成对添加数字。然后将结果成对相加。再次成对添加这些结果,依此类推,直到剩下两个要添加的数字。
很简单:使用更高的精度。使用 long double 计算双精度数的总和。使用 double 计算浮点数的总和。
接近完美:查看前面描述的 Kahan 算法。最好还是从最小的数字开始添加。
对于一般情况,我会使用补偿求和(或 Kahan 求和)。除非数字已经排序,否则排序将比添加它们更昂贵。补偿求和也比排序求和或朴素求和更准确(参见上一个链接)。
至于参考资料,每个程序员都应该知道的关于浮点运算的知识涵盖了足够详细的基本要点,以至于有人可以在 20 (+/- 10) 分钟内阅读并理解基础知识。Goldberg 的“每个计算机科学家都应该知道的关于浮点运算的知识”是经典参考资料,但我认识的大多数推荐这篇论文的人自己都没有详细阅读过它,因为它大约有 50 页(更多,在某些印刷品),并且用密集的散文写成,所以我很难推荐它作为人们的第一线参考。再看一遍这个主题是很好的。百科全书参考是 Higham 的数值算法的准确性和稳定性,其中涵盖了该材料,以及许多其他算法中数值误差的累积;它也是 680 页,所以我也不会先看这个参考。