Accurate sum and dot product
Takeshi Ogita, Siegfried M. Rump, Shin'ichi Oishi
Algorithms for summation and dot product of floating point numbers
are presented which are fast in terms of measured computing
time. We show that the computed results are as accurate as if
computed in twice or K-fold working precision, K >= 3. For
twice the working precision our algorithms for summation and dot
product are some 40 % faster than the corresponding XBLAS
routines while sharing similar error estimates. Our algorithms are
widely applicable because they require only addition, subtraction
and multiplication of floating point numbers in the same working
precision as the given data. Higher precision is unnecessary,
algorithms are straight loops without branch, and no access to
mantissa or exponent is necessary.
SIAM Journal on Scientific Computing, 26:6 (2005), pp. 1955-1988.