Paper Info
Title
Accurate Floating-Point Summation Part I: Faithful Rounding
Abstract
Given a vector of floating-point numbers with exact sum $s$, we present an algorithm for calculating a faithful rounding of $s$, i.e., the result is one of the immediate floating-point neighbors of $s$. If the sum $s$ is a floating-point number, we prove that this is the result of our algorithm. The algorithm adapts to the condition number of the sum, i.e., it is fast for mildly conditioned sums with slowly increasing computing time proportional to the logarithm of the condition number. All statements are also true in the presence of underflow. The algorithm does not depend on the exponent range. Our algorithm is fast in terms of measured computing time because it allows good instruction-level parallelism, it neither requires special operations such as access to mantissa or exponent, it contains no branch in the inner loop, nor does it 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 algorithm are proved to be optimal.
Year
DOI
Venue
2008
10.1137/050645671
SIAM J. Scientific Computing
Keywords
Field
DocType
distillation,error-free transformation,faithful rounding,extra precision,maximally accurate summation,error analysis,accurate floating-point summation part,high accuracy,floating-point number,computing time,double precision,immediate floating-point neighbor,standard floating-point addition,working precision,algorithm adapts,xblas,exact sum,condition number,floating point
Arithmetic underflow,Condition number,Floating point,Double-precision floating-point format,Algorithm,Rounding,Multiplication,Logarithm,Mathematics,Significand
Journal
Volume
Issue
ISSN
31
1
1064-8275
Citations 
PageRank 
References 
62
4.54
26
Authors
3
Name
Order
Citations
PageRank
Siegfried M. Rump1774102.83
Takeshi Ogita223123.39
Shin'ichi Oishi328037.14