addition instead of subtraction in Kahan algorithm

Question

This is the Kahan summation algorithm from Wikipedia:

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

Is there a specific reason why it uses subtraction (as opposed to addition)? If I swap the operands in the computation of c, can I use addition instead? Somehow, that would make more sense to me:

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

Or is there some weird difference between floating point addition and subtraction I don't know about yet?

Also, is there any difference between (t - sum) - y and t - sum - y in the original algorithm? Aren't the parenthesis redundant, since - is left-associative, anyway?

Answer 1

As far as I can tell, your method is exactly equivalent to the one from Wikipedia. The only difference is that the sign of c -- and therefore its meaning -- is reversed. In the Wikipedia algorithm, c is the "wrong" part of the sum; c=0.0001 means that the sum is a little bigger than it should be. In your version, c is the "correction" to the sum; c=-0.0001 means that the sum should be made a little smaller.

And I think the parentheses are for readability. They're for us, not the machine.

Answer 2

Your two algorithms are equivalent. The only difference during execution will be the sign of c. The reason it uses addition is because in Kahan's version, c represents the error, which is conventionally the correct minus the computed value.

In the sense that parentheses specify the order of operations, the parentheses are absolutely necessary. In fact, they are what makes this algorithm work!

When subtraction is left-associative, as it is in most languages, a - b - c evaluates as (a - b) - c so the two are the same. But the subtraction in the Kahan algorithm is a - (b - c), and that should not be evaluated as a - b + c.

Floating-point addition and subtraction are not associative. For expressions that are equivalent in standard arithmetic, you may get different results depending on the order in which you perform the operations.

Let's work with 3 decimal digits of precision, for the sake of clarity. This means that if we get a result with 4 digits, we have to round it. Now compare (a - b) - c with the mathematically equivalent a - (b + c) for some specific values:

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

with

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

So the second approach is less accurate.

In the Kahan algorithm, t and sum will usually be relatively large compared to y. So you often get a situation like in the example above where you would get a less accurate result if you don't do the operations in the correct order.