#include <iostream>
float naive_sum( const float* arr, int n )
{
float sum = n ? arr[0] : 0.0 ;
for( int i = 1 ; i < n ; ++i ) sum += arr[i] ;
return sum;
}
float kahan_sum( const float* arr, int n )
{
double sum = n ? arr[0] : 0.0 ;
double correction = 0.0 ;
for( int i = 1 ; i < n ; ++i )
{
double corrected_val = arr[i] - correction ;
double new_sum = sum + corrected_val ;
correction = (new_sum - sum) - corrected_val ;
sum = new_sum;
}
return sum;
}
int main()
{
const float arr[5] = { -1e10, -11.6, -10.0, +10.0, +1e10 } ;
std::cout << "naive summation: " << naive_sum( arr, 5 ) << '\n'
<< "compensated summation: " << kahan_sum( arr, 5 ) << '\n' ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKZmxvYXQgbmFpdmVfc3VtKCBjb25zdCBmbG9hdCogYXJyLCBpbnQgbiApCnsKICAgIGZsb2F0IHN1bSA9IG4gPyBhcnJbMF0gOiAwLjAgOwoKICAgIGZvciggaW50IGkgPSAxIDsgaSA8IG4gOyArK2kgKSBzdW0gKz0gYXJyW2ldIDsKCiAgICByZXR1cm4gc3VtOwp9CgpmbG9hdCBrYWhhbl9zdW0oIGNvbnN0IGZsb2F0KiBhcnIsIGludCBuICkKewogICAgZG91YmxlIHN1bSA9IG4gPyBhcnJbMF0gOiAwLjAgOwogICAgZG91YmxlIGNvcnJlY3Rpb24gPSAwLjAgOwoKICAgIGZvciggaW50IGkgPSAxIDsgaSA8IG4gOyArK2kgKQogICAgewogICAgICAgIGRvdWJsZSBjb3JyZWN0ZWRfdmFsID0gYXJyW2ldIC0gY29ycmVjdGlvbiA7CiAgICAgICAgZG91YmxlIG5ld19zdW0gPSBzdW0gKyBjb3JyZWN0ZWRfdmFsIDsKICAgICAgICBjb3JyZWN0aW9uID0gKG5ld19zdW0gLSBzdW0pIC0gY29ycmVjdGVkX3ZhbCA7CiAgICAgICAgc3VtID0gbmV3X3N1bTsKICAgIH0KCiAgICByZXR1cm4gc3VtOwp9CgppbnQgbWFpbigpCnsKICAgIGNvbnN0IGZsb2F0IGFycls1XSA9IHsgLTFlMTAsIC0xMS42LCAtMTAuMCwgICsxMC4wLCArMWUxMCB9IDsKICAgIHN0ZDo6Y291dCA8PCAibmFpdmUgc3VtbWF0aW9uOiAiIDw8IG5haXZlX3N1bSggYXJyLCA1ICkgPDwgJ1xuJwogICAgICAgICAgICAgIDw8ICJjb21wZW5zYXRlZCBzdW1tYXRpb246ICIgPDwga2FoYW5fc3VtKCBhcnIsIDUgKSA8PCAnXG4nIDsKfQo=