Re: MidRad and reproducibility
Vincent Lefevre wrote:
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).
But this is too vague for a serious discussion.
Those who want midrad in the standard must come up with meaningful
proposals for what to standardize and how.
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).
I do not understand the formula. Please explain.
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.
[0,2r]*[0,2r]=[0,4r^2] has a width of 4r^2 but the centered product
<r,r>*<r,r>=<r,3r^2> has a width of 6r^2, so the width is
overestimated by a factor of 1.5, even for tiny r.
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).
In this case, the multiprecision part costs O(N log N) and the
bounding part costs O(1) both for midrad and for triplex.
This means that for high precision the bounding part is negligible,
no matter how it is done.
In my opinion, this favors triplex, since that hasn't the disatvantages
of midrad for large intervals.
Arnold Neumaier