[std-interval] Interval comparison operators

[first.i.last at comcast.net]

Dear Prof. Corliss,

While I am quite interested in the issues you raised, I fear that the proposal team may not share that interest.  So I am responding privately in order to avoid the censure that an open discussion would court.

Liberal snippage in effect.

 -------------- Original message ----------------------
From: George Corliss <George.Corliss at marquette.edu>
> 
> On 5/28/06 12:02 AM, "first.i.last at comcast.net" <first.i.last at comcast.net>
> wrote:
> 
> >  -------------- Original message ----------------------
> > From: Guillaume Melquiond <guillaume.melquiond at ens-lyon.fr>
> >>  Now we are interested in what the opinions of
> >> other interval developers are. Should the user be allowed to
> >> compare intervals in C++? And if so, what should the semantic
> >> of these comparisons be?
> > 
> Some reactions ...
> 
> Copyright: Since I intend to quote portions of your document, I assert that
> the quoted portions are subject to: "Permission is hereby granted to
> distribute this document to all past, present, and future members of the
> mailing list <std-interval at compgeom.poly.edu>; all past, present, and future
> members of the team proposing the adoption of intervals into the C++
> language; and all past, present, and future members of the C++ Standards
> Committee and staff thereof.  Any such reproduction, distribution, or
> copying of this document must include the above copyright statement and this
> permission paragraph.  All other reproduction, distribution, or copying of
> this document requires specific, written permission of the copyright
> holder."
> 
> Personally, find find the requirement to include that
> slightly cumbersome.

That's hardly accurate.  It is a royale PITA all the way around.

> However, I consider it a STRONG endorsement to
> the C++ committee of the interest in an interval
> standard that your firm cares enough about intervals
> to be that protective.

An interesting perspective.  I hope the committee sees things that way.

>  Hence, I joyfully comply with your copyright notice
> (I hope).

Technically you did not because you omitted the actual copyright declaration.  ;-)

It's far more of a hassle than it first appears.  :-(

> 
> I'd even allow a modest delay in adoption, if we can
> develop a consensus on what "right" is.

I have hopes in that direction, but am skeptical.  Do you have reason to believe that a consensus is possible?  My understanding is that the FORTRAN proposal failed due to conflicts within the interval community.  I have no evidence to indicate that those conflicts have been resolved.  I fear that the disclosure of our approach to the issues may create additional conflicts.

> 
> 
> Principal Value Model: Hmmm.  Very interesting.  The purist
> side of me is appalled; the engineering side of me applauds.
> I agree that it can be a stepping-stone.  I fear that it allows
> the less-than-careful programmer to violate containment,
> which I consider the touch-stone of interval
> algorithms.

We are extremely interested in any example you have or find of a way to mis-use the proposed functions that produces a containment violation.  Of course they make better damned fools every year, so we are certain that nothing can be foolproof.  

> I'd have to try it out in a non-trivial application
> to see which side is stronger.

It may help to consider the difference in approach to numeric software that differentiates the PV model from classical interval designs.  In brief the classical interval designs are very careful about what is known and what is not known.  The value of outward rounding is that it efficiently provides an explicit boundary on the known/unkown which can be used in a sophisticated system to produce provably-good results.

The PV model is based upon the opposite approach.  Most numeric software is hopelessly bad.  Floating point is notoriously difficult to "get right", and even when you know how it takes a great deal of effort.  Intervals cannot cure that problem.  As you have written one cannot transform a point algorithm into an interval algorithm by substitution of intervals for floating point types.

But intervals can help.  Substitution of triplex numbers for floating point types does not alter the results of a calculation.  It does yield a bound on the error associated with the result.  That additional information, even if not used by the software, but simply reported as an output, is a tremendous improvement over the typical abysmal state of numeric software development.

Once you have triplex numbers in use then it becomes much easier to find and fix the bad parts of a software system.  In the limit you can gradually transform the software into a robust system for numerics.

The PV model arose from the fact that there are two semantics available to the user of triplex numbers.  One can use the point value or one can use the interval.  In fact we have an implementation where the semantics can be determined at run time, so a particular function can be exercised in both modes to determine what effect the change in semantics has on the result and the process by which the result is produced.

But what does it mean to "use the interval" in a typical numeric software package?  We needed a specification for intervals equivalent to the IEEE-754 for floating point types.  One that completely defined the results of every operation at the lowest level.  And one that was completely consistent.  That specification is deferred rounding.  Given deferred rounding, the principal value model does the same thing for intervals that round-to-nearest does for floating point -- it minimizes rounding error.

The initial goal was to get intervals into typical software development without the steep initial ramp required for classical intervals as used in reliable computing.  We succeeded in that because we found a seven-step process that takes an existing system using floating point and converts it to use intervals.  No source code changes needed.

The interesting thing about the conversion process is that the seven steps aren't large.  They are baby steps so simple that it is possible to test the system at each step of the conversion to determine that it still works as it originally did and fix anything that was broken by the conversion.  I/O and all.  Including <stdio.h>.  The only thing we do not support is overwriting numeric objects (via pointer casts, abuse of unions, binary IO, etc.).

But along the way we found that the PV model is so much better than classical floating point that it has very serious utility in its own right.  I would be interested in your reaction to the whole system once we are able to make it available.

> "Empty interval arguments should always yield false."
> and following. Then you are including "I don't know"
> with FALSE?

Nit: "I don't know" is not appropriate.  It suggests that there is or might be an answer that is either true or false but whose actual value is unknown even though knowable.  More accurate alternatives would be "I can't (ever) know", "meaningless" or "Bzzzzt -- bad question" (same as "meaningless").  Note that it does _not_ mean "indeterminate".

This is an interesting point, but it is not limited to intervals.  How about tan(pi/2)? sqrt(negative underflow)?  What is the ratio of one to zero (and no B.S. about limits)?  Any sane answer is complex because the result is undefined within the working number system.

Similarly, an empty interval does not have any relationship with any other interval.  Nor does it have any of the properties of an interval.  Since "undefined" is certainly not "true" it has to be lumped in with "false" if you ask a boolean query

>  Or TRUE means, "I am sure this is true," and FALSE means,
> "I cannot assert TRUE."  I can live with that, but I assert
> that is not the common understanding of FALSE.

I suspect the common understanding of false is defective.  Fuzzy systems have built a lot of good stuff on that defect.

> 
> I prefer exception-free (or exception-nearly-free) execution,
> too, but I think you lose valuable information to lump
> "I don't know" with FALSE.

I disagree.  If you ask an inappropriate question {such as plt([1],mpty)} you have not "lost" information due to the limitations on the response.  The info is still available if you ask a more sensible question {such as isempty(mpty)||plt([1],mpty)}.

IMHO the real issue appears to be how much support developers get in detecting inappropriate queries.

> Tough issue.  I'll be interested to see whether we approach consensus.

Definitely tough politically.  But even assuming the use of exceptions does not let us avoid finding a good answer.  When exceptions are disabled (e.g., in the no-throw() version) we still need to produce a sensible result.

> "If improper intervals are not considered empty then
> improper intervals should also always return false."
> By "improper interval." do you mean semi-infinite, e.g.,
> [1, inf]?

That was not my intent.  I don't comprehend what is improper about [1,inf].  Nor do I consider them to include infinity (another discussion some other time).

By "improper" I meant one whose lower bound was greater than its upper bound.  The typical response of "undefined behavior" is probably not acceptable in this context because we are looking for rigor rather than ease of implementation.

> > George Corliss wrote:
> > 
> >> #1  In my own interval programming work, I don't think
> >> I have ever used certainly/possibly operators or
> >> tri-valued logic, mostly because I have to think too hard.
> >> Instead, I use <double> tests on interval endpoints, e.g.,
> >> lo(A) <= hi(B), and similar.  I must think carefully through
> >> all cases, but boolean tests work as I am familiar.  I think
> >> I am not alone in that practice.  I believe it leads to code
> >> that is more easily maintained by people with only
> >> intermediate expertise.
> > 
> > This is an effective endorsement of the KISS principle.  We agree that
> > comparison operations need to be as simple, clear, and readable as possible.
> > We believe that expresion templates or any other specialized technique, e.g.,
> > exceptions, that is not widely used in other comparison contexts will retard
> > the widespread use of intervals.
> > 
> > Devil's Advocate question: how much of your habitual resistance to the use of
> > higher level comparisons is due to the non-portability of the various
> > implementations?  AFAICT tests of the bounds are the only reliable
> > cross-platform conventions, so they may be the only reasonable habits at
> > present.
> Answer to DA: None.  Even comparing endpoints has slightly
> different syntax in different packages.
> 
> I'm an old Fortran programmer (in any of several
> parsing alternatives).  My habits were formed long ago,
> when I wrote several of my own packages,
> thinking they were for my own use, unconstrained
> by the practices of others. Comparing endpoints gave
> me all the tools I ever needed.  In retrospect, I
> think that habit encouraged me to think carefully
> through sometimes exhaustive cases.  My codes
> are full of segments including character
> graphics suggesting various cases of endpoint comparisons.
>    //    [===========]
>    //              [========>>>
> I think at least I understand what I am doing.
> 
> I do not oppose more sophisticated comparisons as
> you propose.  However, I am likely to advise non-experts
> to save themselves the effort of understanding interval
> comparisons by restricting themselves to endpoint
> comparisons until such time as they feel stifled.  But that's
> a question of habit, as you suggest below.

I think Ron Avitur suggested it actually.

I think your suggestion re restraint until confidence grows is sensible when the domain is classical IA for reliable computing.  But the PV models are designed to be used "out of the box" as replacements for floating point comparisons.  OTOH, even with the Knuth variants it would be wise to make new users code their tolerance/epsilon tests explicitly until they have digested the concepts and can appreciate the higher-level concepts expressed by the comparison functions.  Note that the most important reason to use the higher-level comparisons is to make the code readable by others.

But for adoption in C++ I suspect powerful, succinct concepts are what will make the proposal fly.

> >> #2  I do NOT favor making it as easy as possible for
> >> programmers to take legacy code, change double to
> >> interval, and expect to get anything sensible.
> > 
> > This is a properly cautionary warnng, but with respect
>>  to comparison operators, we disagree.  The warning
> > applies to retaining point-wise algorithms instead of
> > adopting interval algorithms.  We do not believe it
> > applies to primitive operations.  Rather, primitive interval
> > operations should be as similar as possible to built-in 
> > floating point operations.
> The question, "Is A < B?" is different for floating point
> numbers A & B and for intervals A & B.  As evidence of
> that assertion, I submit your document, at least 25 years
> discussion in the interval community, and the fact that so
> many variants exist.

Stipulated.  But observe that your statement applies to classical interval arithmetic rather than the PV-based "duplex" arithmetic.  For PV-based arithmetic the expression "A < B" is the same for floating point and "duplex" numbers.

> 
> Having primitive interval operators that LOOK like primitive
> floating-point operators, but have different semantics OR
> that potentially violate containment requires careful
> consideration.

Yeah.  There's the rub.  No matter how good/useful the PV model is having them along side the classical interval relations is going to cause confusion.  The concepts are quite distinct, but I have oscillated from a desire for full integration to a desire to a completely separate naming convention (e.g., duplex numbers with all interval functionality rewrapped, repackaged, and repainted) many times.  The decision as to which is the most appropriate to propose is a bit of cart-before-horse.  The experiential data required to make a wise decision requires a great deal of exposure/usage by the target population.  But once that experience has been gained it becomes difficult to correct any mistakes in the original proposal.

I'm not that worried about containment violations (can you suggest how they might evolve?) but I am concerned about misuse due to misunderstood complexity -- too many choices.

> 
> If the floating-point and the interval question are different,
> ANY syntax for posing the question is potentially confusing.
> That is why I asserted above I'd even accept a modest
> delay in adoption, if we can develop a consensus on what
> "right" is.

Agreed, with the proviso that consensus on this kind of issue is no guarantee of wisdom.

> 
> That said, your proposal is a good step in that direction.
> When I say "potentially violate containment," I agree that
> your comparisons, used as you intend, are (probably) safe.
>  My fear is that they may be easy to miss-use.  I fear WAY
> too many examples of people writing code with violations
> of containment and blaming us, rather than themselves.
>  I want to make if hard to violate containment, even by
> miss-informed programmers.

I think we agree, but we might not.  I see the threat of naive programmers using the wrong function and thus getting a wrong answer.  But that does not create a containment violation as I understand the term.  Am I missing something?

> > Ron Avitzur wrote:
> > 
> >> I suppose it's only a matter of habits though. People who
> >> are used to handling bounds directly will keep handling bounds
> >> directly, while people who are used to multi-valued logics will
> >> keep using them, and so on. So, in a sense, the question could
> >> become: into which habits do we want people who are new to
> >> interval arithmetic to get? Personally, I wouldn't mind students
> >> using possibly / certainly so that they have to think about what
> >> they really want to express rather than directly going to lower
> >> level manipulation of bounds :-).
> I agree it is a matter of habit, where we each see the rationale
> for OUR habit.  Hence, it is wise to support multiple habits,
> UNLESS there is a large complexity cost.

There is not a large compile or run-time compleity cost.  There might be a perceptual or cognitive complexity cost.

The full triplex arithmetic has about eleven (11) distinct sets of comparison functions.  I don't find that complex because I comprehend each of the models on which they are based.  But if I spent 11 minutes describing them to an accomplished programmer, even an experienced interval arithmetic developer they would walk away hopelessly confused.  I'd guess it would take two hours to present them all intelligibly.  And 4-6 hours of problem sets to insure retention.  That's a lot.

This stuff is not simple.  We need powerful, abstract concepts to encapsulate the complexity and make it usable.  It is possible that C++ concept_maps might solve a lot of this packaging problem.

> > The answer to that question forms the criteria that should
> > be used to evaluate the entire interval proposal, particularly
> > interval comparisons.  My company has spent a great deal
> > of effort attempting to make it easy for C++ users to
> > incorporate intervals into their programs, but our results are
> > will not be ready for release for some months yet.
> Wonderful.  You may not wish to say, but if you did sound
> usability testing and can (eventually) publish your results for
> peer review, any reservations I have for your proposal
> would disappear.

We have some interest from the science departments at Harvard and have discussed a formal usability test to be performed by American Institutes for Research (specialists is human factors evaluation).  But neither of those projects can be actually started until we complete the implementation -- we probably won't have funds to repeat the projects if a major revision is needed.

Our testing philosophy is based on certification rather than evaluation.  We expect to find and fix all of the problems before we get into the field.  So we do a great deal of internal testing.  When we get independent test results they either pass/certify the results we expect or we go back to the drawing board and start over.  We are not comfortable with last-minute patches.

We definitely want as much rigor in the independent evaluations as we can get.

The bulk of this problem is not the functionality, but how to package and describe it to the user.  So it is basically a doc problem.  And the secret to good doc is the same as the secret to any kind or writing: lots of rewriting.  So that's what we do.

> > It may be worth soliciting an opinion from the author of the Frink programming
> > language.  He added support for interval arithmetic in the form of triplex
> > numbers a year or so ago.  His implementation is perfectly straightforward and
> > lacks many of the features of other interval arithmetic implementations.  But
> > due to the simplicity of his implementation he may be able to offer useful
> > insiight into the issue of making intervals easy to use safely.
> Good suggestion.  Have you approached him?

I have not.  I thought that decision should lie with the proposal team.

>  If not, may I or someone else use your message and
> your "Comparison of Intervals in C++" to approach him?

It appears that he is now a member of the mailing list so you are welcome to discuss any part of that paper with him.

Note that Frink only supports point semantics for its triplex numbers, so it does not have the PV-based comparisons.  I made the suggestion in the hope that he had considered additional functionality and would express an opinion about it that might be useful.

> Lee Winter responds to response from Guillaume Melquiond:
> >> I have taken a quick look at your document and I have a
> >> few questions.
> >> 
> . . .
> 
> Do we all implicitly assume CLOSED line segments, with the 
> possible exception of semi-infinite [a, infinity)?  If whole is
> an interval, it is closed, isn't it, because its complement is
> open (and closed)?  Then is the semi-infinite line segment
> [a, infinity] closed because its complement [-infinity, a) is
> open?

Grrrr.  All of the proposals I have seen assume closed intervals.

But there is a great deal of terminology abuse in the above (another discussion another time).

> >> Concerning your neighborhood model, I disagree. You are
> >> saying that "the certain and possible comparison functions
> >> are based on this model". But somebody performing global
> >> optimization or value-range propagation will use them, while
> >> the intervals are nothing like a neighborhood.  So certain and
> >> possible comparisons should not be associated to a "point
> >> model" in my opinion.
> > 
> > The sticking point here appears to be that "intervals are nothing like a
> > neighborhood".  If they are not, what are they like?  I.e., what conceptual
> > model do you believe the certain/possible comparisons to be based upon?  Note
> > that the conceptual models are not used to describe to high levels of the
> > software such as functions, algorithms, programs, or applications.  They are
> > only useful to describe the rationale for having multiple sets of comparisons.
> > So they are properly applied only to distinguish the kinds of low-level
> > operations available.
> Are neighborhoods open or closed line segments?

Closed AFAICT.

> 
> The AGREEMENT here is that a model is necessary to underlie the
> specifications.

Meaning a single model?  I believe that systems like Sun's forte already have at least two models in use (set/segment and neighborhood of uncertainty).  I proposed a third model (PV) for use in "bottom up" improvements to numeric software.

> 
> > But we have a fundamental disagreement.  The reason certain and possible
> > comparisons are characterized as based upon points is that the results of the
> > comparisons describe the presence or absence of points. Possible comparisons
> > indicate that there exists some point in each object that satisfies the
> > relation in question.  Certain comparisons indicate that there is one (and
> > only one) point that satisfies the relation in question (except of course for
> > cne() which 
> > indicates that there is no point that satisfies the relation).
> > 
> >> 
> >> Do you have some bibliographic references for the principal value model?
> > 
> > Not yet.  That is one of the reasons why it says that it would be
> > understandable if they are not part of the standard.  The reasons for
> > mentioning them at all is that it may benefit the team making the proposal to
> > the committee to be aware that there is on-going research and development in
> > this area.  It may be that there should be no operator notation for comparison
> > until the various candidates have been evaluated in the field.  The candidates
> > that have been suggested include set/segment, certainty, and principal value.
> Have you plans to submit something for peer reviewed
> publication?

Interest but no plans.  We do not have experience or skill in that process.

>  Or does that await your commercial release?

Definitely.

We are taking a great risk by the premature disclosure to the C++ standardization effort.  We aren't worried about competition -- the more the merrier.  We are worried about premature evaluation such that when the complete system description is available people will already have made up their minds and dismissed it due to a shallow/incomplete description such as is going on re the standardization proposal.

After all we are going to be making claims that violate most of the existing body of knowledge about interval arithmetic.  So we'll be easy to dismiss as cranks.

> I suspect several likely referees are reading these discussions.

I do not doubt it.

> 
> In my opinion, not-yet-published views deserve consideration, but
> consideration more careful than published concepts.

Of course.

> I suspect the level of community oversight may be higher
> in this forum than in many review processes, so I am open
> to a position paper on the principal value model.

In addition to lack of skill and experience, we also lack bandwidth.  You want to volunteer?  An objective and thorough white paper would be quite valuable to us.
 
> >> Also you are saying this model appeals to a "much wider
> >> audience"; could you give some examples where it is used?
> > 
> > At present it is not used AFAIK.  But one of the claims is that the PV model
> > makes intervals suitable for direct replacement of built-in floating point
> > types (in the sense of the Liskov substitution principle).   If that claim is
> > valid then the PV model makes intervals appeal to every C++ programmer who
> > uses built-in floating point types.
> AFAIK = As Far As I Know?

Yes.

> 
> >> Later, you say that "empty interval arguments should always
> >> yield false". This statement contradicts your line-segment
> >> model, since the empty set is included in every set.
> > 
> > What is the contradiction?  Equivalence and ordering comparisons do not deal
> > with subsets.  The functions in() and contains() should affirm that an empty
> > interval is included in every other interval.  But the empty interval is
> > neither less then nor more than any other interval.  And given the the empty
> > interval is not part of the machine number line one can claim that it is Not
> > an Interval (NaI).  So, just as NaN is not equal to any other floating point
> > value, not even an identical NaN, NaI should not be equal to any other
> > interval, not even an identical NaI.
> > 
> > In fact this conflict illustrates some of the problems caused by the
> > interval-as-set terminology.  It suggests that an empty interval is an empty
> > set, and so seq(empty,empty) should return true.  But the interval-as-segment
> > terminology suggests that an empty interval is not a segment.  (Nor is it a
> > point.  The width is not zero, it is NaN).
> In my Real Analyis class many years ago, I was told that inf(empty) =
> +infinity.

Presumably that was before in-band error values such as NaN were available.  That kind of convention is still in use in both C and C++ in the <math.h> symbol HUGE_VAL.  In specific situation you describe with lower(empty)>upper(empty) the properties indicate that empty is an improper interval, so while the properties were well defined, they were not meaningful.  

Is that a violation of interval consistency?  Is that a lie?  IMHO it is, but only a white one -- i.e. not hidden and justified by necessity.

>  I do NOT suggest that means empty == whole, but it might suggest
> width(empty) = infinity.

I suggest that extension of that concept indicates width(empty) = -infinity rather han +infinity.  That difference is probably the more recent availability of affine systems whereas most legacy systems that even have an infinity were projective.

> 
> The answer to width(empty) = ? Does not matter.  What matters is that we are
> able to specify operator returns which
>    are internally consistent, and
>    do not lead to violations of containment.
> The best (only?) way to achieve that is to have a single, sound underlying
> model.

That's a blivet.  Certainly soundness of the underlying theory is a necessity.  But the theory cannot have a single conceptual model because there is more than one way to view/use/interpret an interval.  There are at least two mutually incompatible such models widely used within the existing community of interval practitioners.  I expect we will have to settle for well defined operations over intervals, and all based upon outward rounding and containment.  But we'll have a variety of operations not all combinations of which will be useful.

Formally we have to expect that because any useful interval system is as least as powerful as basic arithmetic [Godel] and the language of which it is a part is complete [Turing].

> 
> > So based upon the interval-as-segment terminology seq(empty,empty) should
> > return false.
> > 
> > Is there a case to be made that empty intervals are less than or greater then
> > non-empty intervals?
> TRUE means, "I am sure this is true," and FALSE means, "I cannot assert
> TRUE."  That is your convention?

That is the convention I suggest should be used.  I'll take the blame for it, but I would be hesitant to take credit for it.  It is common in many domains.

> 
> >> It also goes against your neighborhood model, since the
> >> classical interpretation is: if something is not possible,
> >> then its contrary is certain (and reciprocally).
> > 
> > The classical interpretation fails anytime a NaN is encountered because they
> > are not part of the number line.  Similarly empty intervals are not intervals
> > (they need have no sensible bounds nor center/radius).  Moreover the classical
> > interpretation cannot be applied to intervals at all because there are more
> > relationships among intervals than there are among points on the machine
> > number line.
> NaN is taking a critical role in this discussion.

Not as a necessary component of intervals, but as a model for the consistent extension of a system.  I raised the the topic of NaN to indicate that the classical interpretation of logic (where !false implies true) already does not apply to modern numerics.  So insisting upon the classical interpretation within interval operations is a serious mistake.

> There is some sentiment to minimize dependence on NaN in the interests of
> speed, although my understanding of the examples is missing.  One problem,
> as I recall, is that in IEEE 754 arithmetic, -infinity + infinity yields
> NaN, while we might prefer, at least in outwardly directed rounding modes,
> to get whole.

I understand that desire and can sympathize.  But it is a containment violation.  The interval [-inf,+inf] does not contain all possible results of operations on intervals.  In only contains the numeric results.  So using it in place of the IEEE-defined result is unacceptable if the goal is complete rigor.

If one is willing to ignore non-numeric results then [-inf,+inf] is a panacea.  But ignoring non-numeric results is not acceptable because it to bad software.  This is directly related to one of the aspects of the incompleteness of Pryce's cset paper.  I don't know where we've gotten on that, but I will find out.

> 
> I recall someone telling me that IEEE 754 NaN admits multiple bit patterns.
> Hence, rather than overloading NaN as we seem to be doing, we might have
> several NaNs, each with distinct meanings, all of which propagate as IEEE
> 754.  I suspect that is a BAD idea because propagation of different NaN bit
> patterns is probably not portable across hardware.

It is not yet portable.  But it will be.  It is not an important issue though because given two NaN inputs getting either out is good enough even if arbitrary.

IMHO we should not worry about bad hardware.  We should be designing good software and then building machines to execute it.  We should not be designing (and limiting) software to tell bad hardware what to do [Dijkstra '72 I think].

> 
> The standard should specify the syntax and semantics, but not the
> implementation.  However, it would be unwise to specify something whose best
> implementation is "too" expensive, whatever "too" is.

Why?

Changing rounding modes is extremely expensive on commodity hardware.  We can show a trivial hardware change that eliminates the need for mode changes and thus eliminates all of the pipeline flushes that plague interval implementations.  It only requires a single, non-sticky bit in the FPU status register and a tiny amount of logic.  If performance were a grave concern it would be quickly adopted.  But there is little interest in the public discussions about it, even in math fora.

If some CPUs don't handle NaNs quickly, that's too bad for those CPUs.  Other CPUs will handle them quickly.  Any other approach will crippled interval sofware by embedding (and thus tacitly approving) support for bad CPU designs.

> Much of this NaN
> discussion probably does not belong in the standard, although having it
> available for implementers in another form should be a big help in having
> the proposed standard accepted.  This discussion is VERY helpful in
> formulating a wise specification.
> 
> It sounds to me as though reliance on the properties of IEEE 754 NaN buys us
> so many benefits, that we probably prefer to accept any performance penalty
> for now and add to the chorus for improved performance for any NaN
> processing in future hardware.

That is my opinion.

> 
> Does anyone have hard experimental data on the performance costs of NaN?

It does not matter how bad they are today, so those performance numbers are irrelevant to the issues under discussion.

However, as a point of reference, recent intel CPUs are unbelievably bad.  They are documented to be 1000x slower on special values (such as NaN, inf, denorm) than on non-special values.  AMDs recent CPUs are orders of magnitude better on special values, even though their handling of special values has slipped somewhat over time.

> > 
> > I quite understand.  If you believe that the inclusion of PV comparisons would
> > inhibit the development of certified computations you should definitely not
> > add them to your standardization proposal.
>
> I'm intrigued.  I insist on "Thou shalt not lie."  I favor simple.  I favor
> considering carefully constructs which lead the unwary to write code that
> appears to lie.
> 
> Let's continue the discussion.  Who else has opinions?

I think the dynamics of the std-interval forum are not as vigorous as one might find in a typical discussion forum.  That might be on purpose.

-- Lee Winter