Talk:Kahan summation algorithm

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Stub Class Low Priority  Field: Applied mathematics

[edit] Some Comments

The algorithm as described is, in fact, Kahan summation as it is described in [1], however, this algorithm only works for either values of y[i] of similar magnitude or in general for increasing y[i] or y[i] << s.

Higham's paper[2] on the subject has a much more detailed analysis, including different summation techniques. I will try to add some of the main statements from that paper to this article if I find the time and there are no objections.

Pedro.Gonnet 16:51, 5 October 2006 (UTC)

  1. ^ W. Kahan, Further Remarks On Reducing Truncation Errors, Communications of the ACM, 8(1),40
  2. ^ N. J. Higham, The Accuracy Of Floating Point Summation, SIAM Journal of Scientific Computing, 14(4), 783-799

Good points. If a y(i) >> s then the sum will be dominated by that value, and the relevance of adding other terms can be questioned since their contribution is lost well below the edge of the precision of s. If on the other hand, s is some sort of multi-precision accumulator (whose usage involves considerable extra cpu time), all contributions will be included, but the merit of the resulting sum can still be questioned as the accuracy of the larger numbers surely does not extend more than a dozen digits. This doesn't stop accountants from demanding fifteen-digit sums. Anyway, details would be welcome, if only as an added reference.NickyMcLean 19:43, 5 October 2006 (UTC)

[edit] Changing the sign of c

Currently, c is calculated and used like this:

c = (t - sum) - y
y = input[i] - c

Is there a reason for not doing this instead?:

c = y - (t - sum)
y = input[i] + c

—Bromskloss 12:07, 4 August 2007 (UTC)