Re: MidRad and reproducibility
On 2009-09-21 16:37:02 +0200, Arnold Neumaier wrote:
> Vincent Lefevre wrote:
> >On 2009-09-21 14:15:45 +0200, Arnold Neumaier wrote:
>
> >>Can you please give an example of what beyond enclosure you want to
> >>require from an implementation of midrad multiplication?
> >
> >1. Something about the accuracy (i.e. an accuracy mode 'accurate',
> >which would have some additional requirements, and an accuracy
> >mode 'valid').
>
> This would seem possible, although is is not trivial to come up with
> an algorithm-free definition of accurate that is provably implementable
> for +,-,*,and /. What would you suggest?
I agree that this is non-trivial. This doesn't mean that there would
not exist a nice general specification (probably something related to
the condition number of the function).
> >2. Something about the midpoint of an interval. If you evaluate
> >yy = f(xx), what's the relation between mid(yy) and f(mid(xx))?
> >Do we have correct rounding or some error bound?
>
> Please make a specific suggestions of the relation that you'd want
> to see.
Something like mid(yy) = o(f(mid(xx))) with correct rounding or some
error bound (that's the simplest solution, and for applications where
this would be a bad idea, infsup may be a better choice anyway).
> Forcing the two equal forces overestimation in the width of the
> product by a factor of up to 1.5. Would that be compatible with an
> accurate mode?
I don't understand what you mean.
> >I think that since midrad is more targeted at performance-critical
> >applications [in multiple precision] (if performance doesn't matter,
> >infsup should be better), the representation should be left to the
> >implementation.
>
> Please explain why performance could be critical. If you work with
> N digits, an addition/subtraction takes O(N) work while the bounding
> part costs only O(1), and a multiplication takes O(N^2) work while
Actually less than O(N^2).
> the bounding part costs only O(N), whether done with lowprecision
> midrad or with triplex.
Why O(N)? An approximation of the error (overestimated) is sufficient
in practice, so that this would be in O(1).
> Division and elementary functions are surely not less complex.
This would be similar to the multiplication:
* infsup: 2 multiple-precision evaluations[*].
* midrad: 1 multiple-precision evaluation and O(1) for the
bounding part.
[*] In theory, some computations could probably be shared, but IMHO,
this is quite complex (at least for the elementary functions). The
common part of x_lo and x_hi would also need to be shared, but the
representation would be equivalent to infsup. Alternatively, one
might be able to do something like:
shared representation -> midrad -> evaluation/bounding -> shared
representation
with acceptable accuracy (I recall that the goal of midrad was for
performance, so that one can exclude tight accuracy here) and not
much overhead compared to midrad. If this works, this can make
infsup OK for performance in multiple precision.
--
Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / Arénaire project (LIP, ENS-Lyon)