Re: Proposal for a new structure of the standard
> Date: Wed, 14 Jul 2010 02:49:31 +0200
> From: Vincent Lefevre <vincent@xxxxxxxxxx>
> To: stds-1788@xxxxxxxxxxxxxxxxx
> Subject: Re: Proposal for a new structure of the standard
Vincent,
You raise many points here.
Some I agree with.
Some I do not.
Some I'm not sure I understand.
I will not be able to answer them all.
But I will try.
>
> On 2010-07-13 06:43:25 -0700, Dan Zuras Intervals wrote:
> > > * Does IDBar have to be a finite set? This doesn't seem to be really
> > > useful and that would rule out some implementations, such as
> > > intervals of GMP integers, for instance.
> >
> > Well, two things here.
> >
> > First, no, it does not have to be a finite set. It is
> > just finite in any implementation known or considered &
> > therefore useful in that sense.
> >
> > And, second, that includes GMP. GMP may be able to
> > represent a great many more numbers. But not infinitely
> > many. :-)
>
> According to the *specification*, the numbers are not bounded, thus
> the set is infinite.
I'm not sure what specification you mean here.
That some set at level 2 contains intervals with
unbounded endpoints does not imply that the set
itself is infinite. There may be only finitely
many intervals with unbounded endpoints just as
the set itself may be finite. And IS finite in
all cases that we know of or need to consider.
If you mean that the size of the largest FINITE
element in any given set is finite but unbounded,
this is also true. And no more implies that the
set itself is infinite than does the existence
of finitely many unbounded intervals within it.
But you need not appeal to unbounded endpoints.
You could just as easily appeal to the density
of small intervals surrounding some finite number.
And, again, while there is no limit to how dense
a set of intervals may be, there is a limit to
how dense they get within any given level 2 set.
Note that we are not putting any limits on multi-
precision intervals as a CONCEPT. It is just that
that concept does not live at level 2. What lives
there is the (finite) instantiation of some multi-
precision interval for some precision.
It does not invalidate anything you are saying.
It just means that considering sets at level 2 to
be infinite is not useful to us for defining how
things work there.
Dedekind may have used it. But not us.
That's all.
> One can deduce obvious bounds from the internal
> structure, but I don't think such bounds have any interest as in
> practice, the limit is implied by the available memory, with an
> undefined behavior (in general) when the available memory is
> exhausted.
Of course.
> This is very different from the set of floating-point
> numbers in fixed precision, where the limits (range and precision)
> are well-known and the specification is clear (though there may
> still be implementation limits in practice, e.g. because in general
> some memory will be dynamically allocated).
I would argue against that. The limits of range &
precision are just as clear as they are with smaller,
hardware implemented floating-point numbers. It is
just that in the case of multi-precision intervals
the user is allowed to choose those limits.
But the limits are there all the same.
>
> > > * IMHO, the definition of the hull should not be required. It seems
> > > to be useful only for the tighest arithmetic, and the standard
> > > shouldn't require things that are not used.
> >
> > The definition of the hull is required for uniqueness.
> > Which would be true whether or not tightest arithmetic
> > is in effect.
>
> 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'.
But I think you are using 'hull' in the sense that John
has used it in his paper. Note that John is defining a
slightly different hull than is used in Vienna & for a
different purpose. In 3.4, John is trying to get at the
notion that a hull can & should be defined that gives a
unique result in the sense that all other containing
intervals ('hull' in the Vienna sense) are supersets of
that hull.
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.
We are not trying to say HOW this is to be done. That
was my mistake earlier.
Merely that is must be done.
For lots of reasons.
> And the hull is *not* required for uniqueness. You can define
> uniqueness (but what uniqueness?) with a hull, but there can be
> other ways.
Of course.
For example, 754 made roundToNearest unique in the half
way case by 'rounding to nearest even'. But the decimal
guys like 'round up on even' so we put that one in there
as well when we included them in 2008. There are also
'round down' & "round to nearest odd' as possible tie
breakers.
So one COULD do something like 'round to that interval
for which the midpoint has the most trailing zeros' or
some such thing.
It sounds silly. And maybe it is.
But, as John pointed out, hull alone will not get us
there. So something else will have to be done as well.
Maybe something arbitrary.
Maybe something silly.
>
> > It is also required for reproducibility.
>
> Ditto, it is *not* required for reproducibility. A fixed algorithm
> in a fixed arithmetic (i.e. with no optimizations that can change
> the behavior) is sufficient for reproducibility.
Ah, now we get into what amounts to a philosophical
question. Mostly about how one writes standards.
Should we make our specifications at the level of the
desired properties of the result or should we just go
ahead & fix on an algorithm?
And, if I may be permitted to wax philosophical for a
moment, we are mortal beings of finite wisdom. We may
do some very clever things in our short span on this
Earth, but there will be those that follow who are
cleverer still.
So if we fix on an algorithm for all time we stifle our
intellectual descendents from being able to improve on
our work by denying them the ability to apply their
greater knowledge to it.
But if we define things at the level of the properties
that are required, at the level of principles we are
trying to hold to, at the level of the Reals themselves
& intervals on the Reals, then we open the future to all
those who can find better ways to do things than we ever
dreamed possible.
So, defining an algorithm is possible. But I believe
that defining the set theoretic characteristics is a
better thing to do.
Harder but better.
>
> > Not merely reproducibility among implementations but
> > reproducibility WITHIN an implementation. For without it, how
> > is one to know that this interval is the same as one computed
> > earlier?
>
> With the algorithm that computes it: reproducibility is ensured
> by the underlying arithmetic.
Well, I just expended my daily ration of philosophy
above. So let me answer this one more practically.
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.
I am not concerned with containment here. Merely with
the reasonable expectation that the user may have to
get the same results twice.
Neither am I concerned with the possibility that one
result might look different than the other. On the
contrary, in the context with which I made that
statement I was concerned that the two results might
look exactly the same & yet BE different. Different
in their representation would be OK. But different
in the way they behave in subsequent calculations is
not.
It is the possibility of this 'silent' difference that
must addressed by some reproducibility constraint.
I'm not sure quite how yet. Hull is part of it but
not all of it.
>
> > Should we, as a standards body, decide & specify the
> > algorithm used to compute the hull? Or, if not the
> > algorithm itself, the properties to be met by a hull
> > that provides for uniqueness?
>
> 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'.
Look on page 22, section 3.5, the 3rd bullet item.
As for John's hull, yes, he only uses it for defining
tight constraints.
We will need something for 'valid' arithmetic as well.
Something more constraining than mere containment.
I don't know what yet.
But something.
>
> The obvious use of the hull is just to return the hull of some subset
> defined at Level 1: this is exactly what the "tightest" version does.
> So, if you do not want the "tightest" version, how would you use the
> hull?
The hull is used for all tightness constraints in Vienna.
It gets us containment.
John's hull is used for tight versions for now.
The 'valid' versions use the Vienna hull for containment
& will need something else as well.
After all, we don't want to admit an arithmetic that
returns [entire] for everything. Now, do we? :-)
>
> > > * Should there be a notion of internal and interchange idatatypes?
> >
> > Perhaps there should. But that is a discussion for
> > another day. It need not touch on the issues here.
> >
> > John has gone to great trouble to couch this discussion
> > in terms of level 1 & level 2 notions only.
> >
> > Issues of representation, whether exchangable or not,
> > don't enter into it.
>
> Note: in my question, I meant at Level 2.
Hmm. In 754 we created the notion of an interchange type
for those datatypes for which a standard representation
existed (at level 3). Then we went ahead & defined a list
of such representations for a class of datatypes. It was
the representation that was interchanged.
What do you mean by a concept of interchange at level 2?
>
> > Of course interval arithmetic is not designed to detect
> > bugs in processors. Or anywhere else for that matter.
> > What ever gave you THAT idea?
>
> Then the paragraph on the Pentium bug is meaningless.
Don't blame John for that comment. Blame me. And it
was not about detecting bugs in processors. It was
about companies that let arithmetic bugs get out there
& then deny that they are a problem by saying that only
obscure mathematicians doing obscure mathematics would
ever find it.
It is meaningful to us only in the sense that one could
run a perfectly correct & bug free interval package on
such a machine & STILL get incorrect results.
The FTIA is helpless to guard against that sort of thing.
As it happens, we are not the only finitely wise mortals
on this planet. :-)
>
> > 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.
Prof Kahan told me a few years back that the typical
computer science major graduates these days without
ever having taken a numerical analysis class. Not one.
So you are rare even among professionals in our field.
These are our users. These are our customers. These
are the people trusted by the rest of us not to design
a bridge that will fall down.
This standard is our way of helping them.
And ourselves. :-)
>
> > 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. The interval
implementer. The interval programmer. The data fed to
the problem. The interpretation of the results. And,
yes, the correctness of the hardware as well. And more.
If all these things be true, the FTIA follows.
But if even ONE be not true...
>
> > Quality of an implementation goes a long way to gaining
> > that trust among those who are not trained in formal
> > interval methods. That means how tight a result can be
> > returned by an implementations. It also means how well
> > it works in other ways that go towards trust. Does it
> > have bugs or not? Are the answers returned the answers
> > expected? Can they be understood? Do I believe them?
> > That sort of thing.
> >
> > Reproducibility is part of that. If I get one answer on
> > one machine & another on another, why should I trust
> > EITHER of them?
>
> Because of the FTIA.
We are both mathematicians.
It gives us an outlook on life that differs from the
rest of the world. We know there are infinitely many
primes without having to count them because there is
a theorem to that effect. That theorem is 2300 years
old & just as valid today as it was then. And it will
be true for all time.
We also know some things are false. We know there are
no such things as perpetual motion machines. We do not
have to look at the design of one to know that. It does
not make us closed minded. It does not even make us
skeptics, although there is an aspect of that to it.
But we are also computer experts & engineers. This
colors our outlook too. We both know how easy it is
to make mistakes. We both know how common they are.
We both struggle against them in our own work & can
appreciate fine work of others for knowing how hard it
is to accomplish. So when someone creates a system
that provably expresses some theorem like the FTIA we
know that is a non-trivial accomplishment.
But we are not selling (if that is the word) interval
systems to each other. We are selling them to the rest
of the world.
The rest of the world trusts & doubts for different
reasons than we do. It does not make them wrong. But
if we do not address those trusts (which are misplaced)
& doubts (which we should alleviate) we will fail to
win them over.
And we will fail as a standard.
>
> > It has been suggested that in that case the TRUE answer must,
> > therefore, be in the intersection of both. But that is only a
> > valid conclusion if I trust both answers.
>
> There's no reason not to trust them, unless you assume that there may
> be a bug in the implementation or a hardware problem. If you assume
> that at least one of the answers is correct, you can take the union.
> It you don't trust anything, then there's nothing one can do for you.
>
> If you don't trust some implementation, then you should have two
> different implementations. And if you want to detect inconsistencies
> between them, they should implement the tightest version.
>
> --
> Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
Ah, yes: Trust & doubt,
That's what its all about.
We can trust in our brothers,
And have doubt for the others.
We can point to the proofs,
But it won't prevent goofs.
We can loosen our intervals,
if we loosen our principles.
If we seek to gain trust,
higher goals are a must.
As for 1788,
We have hard choices to make.
Many arguments, no doubt,
Before this standard goes out.
(Sorry. I couldn't resist. :-)
You can seek to convince a fellow mathematician but
that is only part of your job.
And maybe that is the easy part.
Let me leave you with one final pearl of wisdom Prof
Kahan imparted to me some 3 decades ago. And I will
warn you that wisdom is paid for with sadness.
Prof Kahan said that in our world (speaking of the
world of floating-point at the time), if we do our
job EXTRAORDINARILY well, if we write very accurate
code, design excellent circuits, if we never make a
mistake, if we never let a special case get by us,
if we do all these things right, our reward will be
that no one ever notices.
For it is only the failures that anyone ever notices.
Sadly, I think this applies to us more than it ever
did to the floating-point world.
Dan