wrote:
> 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<times; count++)
>> {
>> y=tosum-c;
>> t=sum+y;
>> c=(t-sum)-y;
>> sum=t;
>> }
>> return(sum);
>>}
>>
>>Could you, please, point where I went wrong?
>>
>>Thanks.
>>
>>Alexandre Aguiar, MD
>>--
>>comp.lang.c.moderated - moderation address: -- 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.
>
>
> typedef struct KahanAdder_t {
> double sum_; /* The current working sum. */
> double carry_; /* The carry from the previous
> operation */
> double temp_; /* A temporary used to capture residual
> bits of precision */
> double y_; /* A temporary used to capture residual
> bits of precision */
Why store the two temporaries in the struct instead of just
using a pair of `auto' variables in add()?
> } KahanAdder_t;
>
> /* After each add operation, the carry will contain the additional */
> /* bits that could be left out from the previous operation. */
> void add(const double datum, KahanAdder_t * kp)
> {
> kp->y_ = 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 <stdio.h>
> #include <stdlib.h>
> 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
lid
--
comp.lang.c.moderated - moderation address:
-- 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.
Similar Threads
