Re: Proposal for a new structure of the standard
On 2010-07-14 00:56:39 -0700, Dan Zuras Intervals wrote:
> > According to the *specification*, the numbers are not bounded, thus
> > the set is infinite.
>
> I'm not sure what specification you mean here.
GMP's (for the mpz_t type). GMP doesn't document any limit on the
size of the integers, so that the considered set is Z. In practice,
there will be limits that depend on the available memory (thus are
not fixed, so that making a specification with limits would be
rather artificial).
And since the set of endpoints is infinite, the set of the intervals
based on mpz_t would be infinite too.
For floating-point, note that there are feature requests for MPFR to
have unbounded exponents, using the mpz_t type for the exponent.
> > In the paper, the hull is *not* used for the "valid" version, thus
> > it is completely useless when only the "valid" version is available.
>
> Hmm. If you are using "valid" in the same sense as it
> is used in the Vienna document, I think you will find
> that hull IS USED for all of 'tightest', 'accurate', &
> 'valid'.
No, of course, I'm using "valid" in the sense of John's paper
(though it has probably more or less the same meaning as in
the Vienna document).
> But I think you are using 'hull' in the sense that John
> has used it in his paper.
Yes, my comments are based *only* on John's paper. We are discussing
about John's paper, not the Vienna document.
> But John also points out (just above 3.4) that hull
> alone will not get us there unless something else is
> done by an implicit type to "make itself explicit".
>
> That means that some interval arithmetics that we are
> trying to get into this standard do not HAVE unique
> intervals that both contain the result & are contained
> by all other containing intervals.
>
> Unless they are MADE TO DO SO.
>
> This is the point John is trying to make here.
But my point is that it isn't necessarily useful. This property
isn't even used in John's paper.
BTW, John's definition of a hull doesn't even ensure uniqueness.
Indeed, consider y = hull(S). The definition of the hull allows
the existence of z such that S is subset of z, and y is not a
subset of z (necessarily, z is not a subset of y either).
Said otherwise, John defines the hull as a minimal element, not
as the least element.
> As it happens, specifying algorithms does not get us
> reproducibility. For, as is often the case with
> parallel algorithms, if we permit an implementation
> to re-associate in two different executions of the
> SAME algorithm we may get two different answers.
That's no longer an algorithm, but a parallel algorithm or
undeterministic algorithm or whatever.
> > Since the hull isn't used for the "valid" version, what's the point?
>
> I mentioned this before. It is used in the Vienna
> document for all tightness constraints, even 'valid'.
Then, John should include that in his paper, and make sure that's
the same hull definition. Until he does, your point is off-topic.
> The hull is used for all tightness constraints in Vienna.
See above, this is currently off-topic.
> What do you mean by a concept of interchange at level 2?
This was mentioned in earlier discussion. For instance, one could
have inf-sup for interchange, and mid-rad internally. Since the
Level-2 sets are different for these representations, that's why
I've said Level 2.
> > > But interval arithmetic IS designed to assure the user of
> > > the correctness of the results that are computed with it.
> > > For were it not so why would any user go to all the trouble
> > > needed to use it? One can always compute faster in some
> > > hardware floating-point. And one can get more digits more
> > > easily computing with GMP, MPFR, et al. But neither of
> > > those methods tell you exactly HOW MANY of those digits
> > > are correct, if any.
> >
> > You can do a static error analysis.
>
> No, Vincent, YOU can do a static error analysis. You
> have both the skills & the training. Most people out
> there do not.
I just said that it is possible.
But note that interval arithmetic may be more pessimistic than
static error analysis, depending on the application (it can also
be less pessimistic on other applications, but anyway...).
Interval arithmetic just gives bounds, and the resulting
interval, though correct, may give no information (e.g. Entire).
> > > Intervals do that for you.
> > >
> > > But only if they are trusted to do so.
> >
> > and you don't need reproducibility/uniqueness/... only the FTIA.
>
> As I mentioned before, FTIA can only be trusted if many
> other things are trusted as well.
This is also true even if reproducibility/uniqueness/... are required.
The non-reproducibility could also be used to detect problems,
e.g. if an empty set is obtained as the result for one of the
implementations, this can mean some error in the user code.
--
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 / Arénaire project (LIP, ENS-Lyon)