Paper Info
Title
Accurate Floating-Point Summation Part II: Sign, K-Fold Faithful and Rounding to Nearest
Abstract
In Part II of this paper we first refine the analysis of error-free vector transformations presented in Part I. Based on that we present an algorithm for calculating the rounded-to-nearest result of s := Sigma pi for a given vector of floating-point numbers pi, as well as algorithms for directed rounding. A special algorithm for computing the sign of s is given, also working for huge dimensions. Assume a floating-point working precision with relative rounding error unit eps. We define and investigate a K-fold faithful rounding of a real number r. Basically the result is stored in a vector Res(nu) of K nonoverlapping floating-point numbers such that Sigma Res(nu) approximates r with relative accuracy eps(K), and replacing Res(K) by its floating-point neighbors in Sigma Res(nu) forms a lower and upper bound for r. For a given vector of floating-point numbers with exact sum s, we present an algorithm for calculating a K-fold faithful rounding of s using solely the working precision. Furthermore, an algorithm for calculating a faithfully rounded result of the sum of a vector of huge dimension is presented. Our algorithms are fast in terms of measured computing time because they allow good instruction-level parallelism, they neither require special operations such as access to mantissa or exponent, they contain no branch in the inner loop, nor do they require some extra precision. The only operations used are standard floating-point addition, subtraction, and multiplication in one working precision, for example, double precision. Certain constants used in the algorithms are proved to be optimal.
Year
DOI
Venue
2008
10.1137/07068816X
SIAM JOURNAL ON SCIENTIFIC COMPUTING
Keywords
DocType
Volume
maximally accurate summation,faithful rounding,rounding to nearest,directed rounding,K-fold accuracy,sign,error-free transformations,distillation,high accuracy,XBLAS,error analysis
Journal
31
Issue
ISSN
Citations 
2
1064-8275
8
PageRank 
References 
Authors
0.89
11
3
Name
Order
Citations
PageRank
Siegfried M. Rump1774102.83
Takeshi Ogita223123.39
Shin'ichi Oishi328037.14