Re: exact dot product
On 2013-05-18 12:37:44 -0700, Dan Zuras Intervals wrote:
> I fear I must disagree with Vincent & agree with Ulrich. Not only
> did the 754 group "not reject (the) requirement" for correctly
> rounded dot product, we supported it. Even in 754 we included
> definitions for dot products, sums, sum of squares, & sum of
> absolute values. (Clause 9.4, reduction operations.)
>
> Alas, Vincent may point out that we did NOT specify them as being
> exactly computed. Indeed, we were not able to at the time, due
> to there being so many 754s out there that did not support it.
> So these functions are defined but without specified result
> precision. (Although we DID specify exceptions in a standard way.)
>
> However, correctly rounded versions WERE our intention. Indeed,
> it is silly to define them just as they would come out of any
> C-compiler.
It would have been as easy to write the requirement in the IEEE 754
text. See below.
> Then, shortly after the standard was published a number of papers
> appeared that show you how to correctly round your result in all
> cases using 754 arithmetic, just a bit of extra precision, &
> some sorting. It is quite clever & not at all difficult to do.
I agree. This was already known. BTW, MPFR has had an exact sum
since February 2004 (dot product isn't much different since the
terms are just twice as wide).
> And, indeed, had we known they were possible (& fast) at the time
> we WOULD have required them as many (perhaps most) existing 754
> implementations have done now.
I haven't read the article, but the MPFR implementation is based on:
/* Reference: James Demmel and Yozo Hida, Fast and accurate floating-point
summation with application to computational geometry, Numerical Algorithms,
volume 37, number 1-4, pages 101--112, 2004. */
That's 2004.
> So it is my hope that we do it under 1788 as well.
So, as this has been shown, you do not need complete arithmetic
to get a correctly-rounded dot product.
--
Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)