Content area
Full text
Computing 76, 279293 (2006)A Generalized Kahan-Babu
ska-Summation-AlgorithmA. Klein, KasselReceived: November 16, 2004; revised: April 20, 2005Published online: November 3, 2005 Springer-Verlag 2005AbstractIn this article, we combine recursive summation techniques with Kahan-Babu
ska type balancing strategies [1], [7] to get highly accurate summation formulas. An i-th algorithm have only O(n(log2(n))i+Digital Object Identier (DOI) 10.1007/s00607-005-0139-x1)
error beyond 1upl and thus allows to sum many millions of numbers with high accuracy. The additional
afford is a small multiple of the naive summation. In addition we show that these algorithms could be
modied to provide tight upper and lower bounds for use with interval arithmetic.AMS Subject Classications: 65G40, 65G30.Keywords: Floating-point numbers, rounding errors, summation algorithm, interval arithmetic.1. IntroductionThe analysis of rounding errors in oating-point arithmetic is an important problem of numeric and computer science. A very good introduction into this topic
can be found in What every computer scientist should know about oating-point
arithmetic [4].In this article, we want do deal with the following basic problem:Given n oating-point numbers x1,... ,xn. Compute their sumS =This is a nontrivial problem, since the summation of many oating-point numbers
always involves rounding. Indeed several algorithms for oating-point-summation
were proposed in the last decades. All proposed algorithms fall into one of three
classes.The simplest possible algorithm uses a FOR-loop to add the numbers.s := x[1]FOR k := 2 TO n DOs := s + x[k]END DOn
k=1xk.280 A. KleinIn the following, we assume that every oating-point-addition x y satises the
bound x y = (x + y)(1 + x,y) mit |x,y| . Under these assumptions we
can bound the difference between the exact sum and the sum s computed by the
FOR-loop by
ns 1xk (n 1)|x1|+n
i=2(n i +1)|xi|k=(see [13]). If the numbers xi are positive we should sort them in ascending order to
minimize the total rounding-error. If the numbers xi have different sign a good but
not necessarily optimal strategy is to sort the numbers increasing to |xi| (see [5]).A signicant improvement in comparison with the basic iterative algorithm is
achieved by recursive algorithms. In these algorithms all binary summation trees
are possible. Thus the general recursive algorithm has the form:(1) Start with a list of n numbers x1,... ,xn.(2) Choose two numbers x and y from this list, remove...