Kahan 算法中用加法代替减法

Question

这是来自维基百科的 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有什么区别吗？无论如何，括号不是多余的吗？因为 - 是左关联的？

Answer 1

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

我认为括号是为了可读性。它们是为我们服务的，而不是为机器服务的。

Answer 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 相比通常相对较大。因此，您经常会遇到如上例所示的情况，如果不按正确的顺序执行操作，您将得到不太准确的结果。