446,234 Members | 1,889 Online Need help? Post your question and get tips & solutions from a community of 446,234 IT Pros & Developers. It's quick & easy.

# Implementation of Kahan sum algorithm

 P: n/a Hi, Given the pseudocode explanation of the Kahan algorithm at http://en.wikipedia.org/wiki/Kahan_summation_algorithm, I tried to implement it in C. It is supposed to minimize the effect of base conversion errors after repeated sum operations. However, the effect is null. The rounding error persists without change. My implementation is: double kahanSum(double input, double tosum, double times) { double c=0.0, sum=input,y,t; int count; for(count=0; count
9 Replies

 P: n/a asaguiar wrote: Given the pseudocode explanation of the Kahan algorithm at http://en.wikipedia.org/wiki/Kahan_summation_algorithm, I tried to implement it in C. It is supposed to minimize the effect of base conversion errors after repeated sum operations. No, it minimizes summation roundoff or truncation errors due to unequal scale factors, not conversion errors. There is no base conversion being done in the summation loop. However, the effect is null. The rounding error persists without change. My implementation is: double kahanSum(double input, double tosum, double times) { double c=0.0, sum=input,y,t; int count; for(count=0; count double kahanSum(double input, double tosum, double times) { double c=0.0, sum=input,y,t; int count; for(count=0; count

 P: n/a asaguiar wrote: Hi, Given the pseudocode explanation of the Kahan algorithm at http://en.wikipedia.org/wiki/Kahan_summation_algorithm, I tried to implement it in C. It is supposed to minimize the effect of base conversion errors after repeated sum operations. However, the effect is null. The rounding error persists without change. My implementation is: double kahanSum(double input, double tosum, double times) { double c=0.0, sum=input,y,t; int count; for(count=0; county_ = datum - kp->carry_; kp->temp_ = kp->sum_ + kp->y_; kp->carry_ = (kp->temp_ - kp->sum_) - kp->y_; kp->sum_ = kp->temp_; } #ifdef UNIT_TEST #include #include int main(void) { KahanAdder_t k = {0}; double d; double standard_sum = 0; size_t s; for (s = 0; s < 10000; s++) { d = rand() / (rand() * 1.0 + 1.0); add(d, &k); standard_sum += d; } printf("Standard sum = %20.15f, Kahan sum = %20.15f\n", standard_sum, k.sum_); return 0; } #endif If you can use C++, here is a Kahan Adder as a template: http://cap.connx.com/tournament_software/Kahan.Hpp -- comp.lang.c.moderated - moderation address: cl**@plethora.net -- you must have an appropriate newsgroups line in your header for your mail to be seen, or the newsgroup name in square brackets in the subject line. Sorry. Oct 5 '06 #3

 P: n/a asaguiar wrote: Hi, Given the pseudocode explanation of the Kahan algorithm at http://en.wikipedia.org/wiki/Kahan_summation_algorithm, I tried to implement it in C. It is supposed to minimize the effect of base conversion errors after repeated sum operations. However, the effect is null. The rounding error persists without change. My implementation is: double kahanSum(double input, double tosum, double times) { double c=0.0, sum=input,y,t; int count; for(count=0; count

 P: n/a On 03 Oct 2006 21:44:35 GMT, "asaguiar" Hi,Given the pseudocode explanation of the Kahan algorithm athttp://en.wikipedia.org/wiki/Kahan_summation_algorithm, I tried toimplement it in C. It is supposed to minimize the effect of baseconversion errors after repeated sum operations.However, the effect is null. The rounding error persists withoutchange. What rounding error? What was your input to the function? What output were you expecting? What output did you get? >My implementation is:double kahanSum(double input, double tosum, double times) The algorithm in wikipedia is for summing several different values. You are summing the value of tosum repeatedly plus the value of input once. That's OK if it's deliberate. >{ double c=0.0, sum=input,y,t; int count; for(count=0; count c=(t-sum)-y; sum=t; } return(sum);} Did you turn off optimization for your compiler based on the warnings in the article? Remove del for email -- comp.lang.c.moderated - moderation address: cl**@plethora.net -- you must have an appropriate newsgroups line in your header for your mail to be seen, or the newsgroup name in square brackets in the subject line. Sorry. Oct 5 '06 #5

 P: n/a asaguiar wrote: Hi, Given the pseudocode explanation of the Kahan algorithm at http://en.wikipedia.org/wiki/Kahan_summation_algorithm, I tried to > double kahanSum(double input, double tosum, double times) { double c=0.0, sum=input,y,t; int count; for(count=0; count

 P: n/a In article

 P: n/a In comp.lang.c.moderated asaguiar Given the pseudocode explanation of the Kahan algorithm at http://en.wikipedia.org/wiki/Kahan_summation_algorithm, I tried to implement it in C. It is supposed to minimize the effect of base conversion errors after repeated sum operations. However, the effect is null. The rounding error persists without change. [...] Could you, please, point where I went wrong? Most likely, you didn't read the stuff at the bottom of that page under "Caution! Beware Optimising Compilers!". -Larry Jones My dreams are getting way too literal. -- Calvin -- comp.lang.c.moderated - moderation address: cl**@plethora.net -- you must have an appropriate newsgroups line in your header for your mail to be seen, or the newsgroup name in square brackets in the subject line. Sorry. Oct 5 '06 #8

 P: n/a dc*****@connx.com wrote: asaguiar wrote: >>Hi,Given the pseudocode explanation of the Kahan algorithm athttp://en.wikipedia.org/wiki/Kahan_summation_algorithm, I tried toimplement it in C. It is supposed to minimize the effect of baseconversion errors after repeated sum operations.However, the effect is null. The rounding error persists withoutchange.My implementation is:double kahanSum(double input, double tosum, double times){ double c=0.0, sum=input,y,t; int count; for(count=0; county_ = datum - kp->carry_; kp->temp_ = kp->sum_ + kp->y_; kp->carry_ = (kp->temp_ - kp->sum_) - kp->y_; kp->sum_ = kp->temp_; } #ifdef UNIT_TEST #include #include int main(void) { KahanAdder_t k = {0}; double d; double standard_sum = 0; size_t s; for (s = 0; s < 10000; s++) { d = rand() / (rand() * 1.0 + 1.0); add(d, &k); standard_sum += d; } printf("Standard sum = %20.15f, Kahan sum = %20.15f\n", standard_sum, k.sum_); return 0; } #endif It might be better to compute a sum whose value is more predictable, and subject to independent verification. With the test above you can observe that the naive and Kahan sums are different and by how much, but you can't tell whether the Kahan sum is "significantly better." (What *should* the sum have turned out to be?) To test my version (Java, so I won't post it here), I used the harmonic series 1/1 + 1/2 + 1/3 + ... But now that I think of it, it might have been better to compute a geometric series 1 + r + r^2 + ..., for two reasons: First, it forces the algorithm to add small numbers to large numbers, where the naive approach is most liable to lose precision and thus where Kahan's method shines. Second, the sum of the first n terms is easy to compute (if pow() is trustworthy) as (r^(n+1) - 1) / (r - 1), so there's a way to assess the accuracy of the answer. -- Eric Sosman es*****@acm-dot-org.invalid -- comp.lang.c.moderated - moderation address: cl**@plethora.net -- you must have an appropriate newsgroups line in your header for your mail to be seen, or the newsgroup name in square brackets in the subject line. Sorry. Oct 7 '06 #9

 P: n/a Dear Dr. Aguiar, Your implementation is correct. The problem could be any or all of three things: the inputs, the way the result is printed, or optimizing away the roundoff errors in what I call simpleSum below. The following implementation of simpleSum enforces rounding after each step. Try printf ("%.18g %.18g", simpleSum (1e15, .1, 1000), kahanSum (1e15, ..1, 1000)). The %.18g displays the full precision of a double. With this example, I found simpleSum erroneously added 125 where kahanSum added 100. Hope this helps. Sincerely, Elan Riesman Acton, Massachusetts void addDouble (double *c, double *a, double *b) {*c = *a + *b;} double simpleSum(double input, double tosum, double times) { while (times-- 0) addDouble (&input, &input, &tosum); return input; } Given the pseudocode explanation of the Kahan algorithm at http://en.wikipedia.org/wiki/Kahan_summation_algorithm, I tried to implement it in C. It is supposed to minimize the effect of base conversion errors after repeated sum operations. However, the effect is null. The rounding error persists without change. My implementation is: double kahanSum(double input, double tosum, double times) { double c=0.0, sum=input,y,t; int count; for(count=0; count

### This discussion thread is closed

Replies have been disabled for this discussion. 