Computing desk
< September 20	<< Aug \| September \| Oct >>	Current desk >

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 21

Do you recognize this algorithm for floating-point addition?

I came across some code that sums the elements of an array of doubles in the following rather curious way:

double sum = 0.0;
double c = 0.0;
double y, t;

for(i = 0; i < arraylen; i++)
    {
    y = array[i] - c;
    t = sum + y;
    c = (t - sum) - y;
    sum = t;
    }

It's reasonably obvious that someone was trying to circumvent the rather notorious problem that, if the array of data being summed contains values of varying magnitudes, the limited precision of the floating-point sum means that smaller values will tend to lose some/all of their precision, perhaps contributing nothing at all to the final sum.

My question is simply: does anyone recognize this particular technique? Does it have a name? —scs (talk) 21:49, 21 September 2021 (UTC)[reply]

That might be Kahan summation. I don't remember how it works well enough to compare in detail. 67.164.113.165 (talk) 05:22, 22 September 2021 (UTC)[reply]

Testing the algorithm on examples designed to result in precision loss with straightforward summation, it appears to work well – often producing the best FP approximation of the sum computed with exact (infinite precision) arithmetic. --Lambiam 06:33, 23 September 2021 (UTC)[reply]

That's exactly it! Thank you very much. —scs (talk) 12:28, 22 September 2021 (UTC) [reply]

Resolved