8

这是来自维基百科的 Kahan 求和算法：

function KahanSum(input)
    var sum = 0.0
    var c = 0.0
    for i = 1 to input.length do
        y = input[i] - c    // why subtraction?
        t = sum + y
        c = (t - sum) - y
        sum = t
    return sum

它使用减法（而不是加法）是否有特定原因？如果我在 的计算中交换操作数c，我可以使用加法代替吗？不知何故，这对我来说更有意义：

function KahanSum(input)
    var sum = 0.0
    var c = 0.0
    for i = 1 to input.length do
        y = input[i] + c    // addition instead of subtraction
        t = sum + y
        c = y - (t - sum)   // swapped operands
        sum = t
    return sum

或者我还不知道的浮点加法和减法之间是否存在一些奇怪的区别？

(t - sum) - y另外，t - sum - y原始算法之间有什么区别吗？括号不是多余的，因为-它是左结合的，无论如何？

4

2 回答 2

2

据我所知，您的方法与维基百科中的方法完全相同。唯一的区别是符号c——以及它的意义——被颠倒了。在维基百科算法中，c是总和的“错误”部分；c=0.0001 表示总和比应有的大一点。在您的版本中，c是对总和的“更正”；c=-0.0001 意味着总和应该小一点。

我认为括号是为了便于阅读。它们是给我们的，而不是机器。

于 2011-12-09T14:38:58.430 回答
2

你的两种算法是等价的。执行期间的唯一区别是 的符号c。它使用加法的原因是因为在 Kahan 的版本中，c表示错误，通常是正确减去计算值。

在括号指定操作顺序的意义上，括号是绝对必要的。实际上，它们是使该算法起作用的原因！

当减法是左结合时，就像在大多数语言中一样，a - b - c计算(a - b) - c两者是相同的。但 Kahan 算法中的减法是a - (b - c)，不应该被评估为a - b + c。

浮点加法和减法不相关。对于在标准算术中等效的表达式，您可能会根据执行操作的顺序得到不同的结果。

为了清楚起见，让我们使用 3 位小数精度。这意味着如果我们得到一个 4 位数的结果，我们必须对其进行四舍五入。现在与某些特定值(a - b) - c的数学等效值进行比较：a - (b + c)

(998 - 997) - 5 = 1 - 5 = -4

和

998 - (997 + 5) = 998 - Round(1002)
                = 998 - 1000 = -2

所以第二种方法不太准确。

在 Kahan 算法中，t与sum相比通常会比较大y。因此，您经常会遇到上述示例中的情况，如果您不按正确的顺序执行操作，您将获得不太准确的结果。

于 2011-12-09T15:15:11.070 回答