Re: exact dot product
On 2013-05-28 12:19:26 +0200, Ulrich Kulisch wrote:
> a number of applications are mentioned in my mails to IEEE P1788 of May 18
> and May 22. Other applications are mentioned in the attachments to my mail
> of May 18 (The paper and poster entitled: "Very fast and exact accumulation
> of products"). Non of these applications can be solved with a correctly
> rounded dot product, i.e., the exact dot product is indeed needed for
> sloving these problems.
Sorry, but there are no details showing your claim. But...
> A fundamental tool of interval arithmetic is "long interval arithmetic"
> sometimes also called "dynamic precision interval arithmetic". It carries so
> many digits that the result always can be guaranteed. (The number of digits
> needed can be obtained by a test run in simple interval arithmetic of by
> trial and error.) I attach a copy of a few pages of my book "Computer
> Arithmetic and Validity". They show how "long interval arithmetic" is
> defined. The definition of the arithmetic operations (and applications also)
> are full of exact dot products. For other fascinating applications see the
> paper [5] on the poster.
Thanks. However P1788 doesn't preclude multiple-precision interval
arithmetic (FYI, I'm particularly interested in it). Definition 9.8
corresponds to an acceptable implicit parameterized interval type.
But P1788 doesn't (and shouldn't) require or recommend some particular
implementation.
With the current CA interface (11.11.11 in Draft 7.1), CA is
associated with some fixed FP format, say binary64, so that even
though multiple precision can be used internally, it is lost at the
end.
For instance, from the first few lines of these pages, if I understand
correctly (this is not very detailed), the inputs can be regarded as
multiple precision values based on some basic floating-point format
(e.g. binary64), so that a dot product of these vectors can be
implemented as a dot product over binary64 only (by algebraic
expansion of the product). If the precision isn't very large (i.e.
if fast multiple-precision multiplication algorithms are not
interesting), I agree that CA can be useful in hardware.
Now, what do you want to do with the CA result?
* Correctly rounding it to the FP format has already been discussed,
and it seems that you want more (otherwise this would just belong to
IEEE 754).
* Keeping it under its exact form? Why? How?
* Converting it back to a multiple-precision value? But how? With the
current interface as specified by Draft 7.1, you can't: you can only
convert a CA value to a FP value. An "extract" operation could be
interesting, e.g. some kind of conversion of a CA value to an n-term
floating-point expansion. So, for instance, CA could be used to
compute accurately a dot product of double-double values... But again
this would impose some given implementation (i.e. CA). On the other
hand, one could say that one has some flexibility to control the
precision.
But even with that, I'm not convinced that CA should be in P1788, in
particular if no processor vendors have shown interest in implementing
CA in hardware.
BTW, how would CA behave in the context of multi-threading when
CA datums need to be transmitted?
> It may well be possible to simulate the functionality of long
> interval arithmetic by multiple precision arithmetic and a correctly
> rounded dot product. But the simplest and fastest way of computing a
> correctly rounded dot product is via an exact dot product:
Probably not in software: one could just compute an approximation
and use something similar to Ziv's method in case of cancellation.
--
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)