Kahan summation algorithm has big computing error when it is compiled by GCC

Question

I use Kahan summation algorithm:

inline void KahanSum(float value, float & sum, float & correction) { float term = value - correction; float temp = sum + term; correction = (temp - sum) - term; sum = temp; } float KahanSum(const float * ptr, size_t size) { float sum = 0, correction = 0; for(size_t i = 0; i < size; ++i) KahanSum(ptr[i], sum, correction); return sum; }

It works fine if it is compiled with using of MSVS, but it has a big computing error when I use GCC.

Where is the trouble here?

What do you mean by big computing error when I use GCC? Could you please elaborate? — abhishek_naik
– abhishek_naik, Commented May 27, 2016 at 14:39
We can get the assembly code ourselves. What we really need, in order to be able to answer this question, is some sample inputs and the expected outputs. And the error message(s) that you're seeing, if any. Like, perhaps, you've forgotten to include the standard library header that defines size_t? — Cody Gray
– Cody Gray ♦, Commented May 27, 2016 at 14:40
The Wiki page has a nice comment: "Beware overly-aggressive optimizing compilers!" Probably you should reduce optimization in this part of code. — Vesper
– Vesper, Commented May 27, 2016 at 14:43

ErmIg · Accepted Answer · 2016-05-27 14:42:52Z

I suppouse, that it's a result of aggresive compiler optimization. So GCC can reduce the expression from:

 float term = value - correction; float temp = sum + term; correction = (temp - sum) - term; sum = temp;

to

 float term = value - correction; correction = 0; sum += term;

because this transformation is mathematically correct, but this optimization kills Kahan algorithm.

In order to avoid this problem you can use "-O1" GCC compiler options to compile the code. It will be something like this:

#if defined(__GNUC__) # pragma GCC push_options # pragma GCC optimize ("O1") #endif inline void KahanSum(float value, float & sum, float & correction) { float term = value - correction; float temp = sum + term; correction = (temp - sum) - term; sum = temp; } float KahanSum(const float * ptr, size_t size) { float sum = 0, correction = 0; for(size_t i = 0; i < size; ++i) KahanSum(ptr[i], sum, correction); return sum; } #if defined(__GNUC__) # pragma GCC pop_options #endif

I see no evidence that GCC is doing the aggressive operations that you describe unless unsafe math optimizations are intentionally enabled (e.g., by throwing the -ffast-math switch). That isn't the default, even at -O3. It cannot be, as far as I know. There are strict rules about floating-point computations.
or use the "volatile" keyword on one of the variables, "temp" for example
@MayurPatel volatile does not work when using -ffast-math with g++ 10

Collectives™ on Stack Overflow

Kahan summation algorithm has big computing error when it is compiled by GCC

1 Answer 1

3 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Linked

Related