[std-interval] extra functions for intervals

[first.i.last at comcast.net]

 -------------- Original message ----------------------
From: George Corliss <George.Corliss at marquette.edu>
> Lee and all,

[...]

> Q1, p. 1, par. 2.  "Standardization of the interval functions
> should not mandate that containment, which is a QoI issue."
>  Do you mean containment in the sense that the set of
> interval standard functions should contain the floating point
> ones?  Or that (shudder) containment of values returned
> should not be mandated?

The latter.  The standard should require that the mathematically correct answer be contained within the interval result.  However, the result of the corresponding floating point function can be arbitrarily far from the mathematically correct answer (QoI of the FP library).  Thus requiring that the FP result be contained within the interval result can have an adverse effect upon the sharpness of the interval result.  So it comes down to a choice between the QoI of the interval implementation versus the consistency between the FP and interval implementations.

We choose consistency for our implementation.  But as much we have a very strong preference for systems that are consistent, we do not believe the standard should make that consistency mandatory because we suspect it would operate to the detriment of the QoI of the interval library.  So we reluctantly suggest that it be left as a recommendation rather than a requirement..  (I would love for 
the consensus to form the opposite conclusion!)

> Q2, par. 4.  "the result of an interval version of a <cmath>
> function is the hull of all of the results ..." is close to the cset
> definition, except that csets enclose also results of limits.

And except that cset theory as I comprehend it considers only the numeric values rather than the full spectrum of function results.

> Several of us are preparing a cset draft for posting here
> within a few days.  _IF_ csets are accepted, say, for
> divide, it would be natural to use them to specify results of
> cmath functions, too?  I'd have to look more closely for
> differences in returned values.

We would love the safe expression rearrangement that a comprehensive cset theory would allow.  And of course that rearrangement should be viable for elementary functions.  So it would appear to be a natural extension of the theory.  But I 
am concerned about the completeness of the theory.  There are function domain issues, the handling of special vaules (Nan & Inf), and the mapping between the real and machine number lines.

The cset issue is certainly bigger than the <cmath> discussion, and might be bigger (or longer) than the standardization discussion. 

> Q4, par. 9. "wrong" and "nacceptably wide"
> --> "wrong" and "unacceptably wide"

Yes.

> Q5. isnan() and nan().  I see where you are going with the
> "Set of interval functions must contain the set of
> floating-point functions, and interval functions on singleton
> intervals must agree with their floating-point counterpart"
> argument.  I'm sympathetic.
> 
> It is a mistake for a standard to give too detailed an
> implementation, but many are concerned that the
> standard also should not mandate a slow implementation.

On whose hardware?  We intend to buy hardware that will execute a good implementation quickly.  People who buy slow hardware should not blame the standard.

Certainly the standard should not mandate an implementation that _cannot_ be executed efficiently.  But we are far from that.

Historical note: One of the very contentious issues in the original adoption of the IEEE-754 standard was that some major vendors (IBM, DEC, etc.) felt that the extra features such as NaN, Inf, and especially denormal numbers would slow down the processing of normal numbers.  The story is that DEC lost a lot of credit as 
a leader in the field when their rep stated categorically that the proposed features _could_not_ be implemented efficiently.  Of course he was wrong, Intel already had an efficient implementation.

Let us not take counsel of our fears.

> I assume we want to represent an <empty> set and
> probably a <whole> set.  If we use [NaN, NaN] as an
> internal, opaque implementation of <empty>, there are
> very few performance-robbing tests.

My understanding is that Sun choose NaNs for empty due to the similarity of the propagation rules for NaN and empty.  Which means that same thing you said above.

But the standard should neither prohibit nor mandate any implementation of empty.  It should describe the properties of empty completely.  In our view all of those properties (lower, upper, midpt, radius, diameter, etc.) are not numbers.  So they should be NaN or HUGE_VAL depending upon the platform capabilities.

> If an implementation DOES decide to use NaN to represent
> <empty>, I guess isnan() does no harm, and I guess nan()
> would be the equivalent of <empty>.

Is there a problem with that?  We tend to view it as a feature.  In fact we support a variety of NaN-based values including:
    "none"   empty
    "init"      uninitialized
    "dead"   destroyed
    "div0"    division by zero
    "imag"   sqrt(negative)
    "EIO "    IO error (read)
    "EDOM" domain error
    "ERNG"  range error

All of these are treated as empty.
    
> 
> Q6.  Additions?
>    interval square( interval X )?

It is a very specific solution to a widespread problem: inconsistent evaluation of dependencies.  Sun uses automatic identity checking which is a slightly more general solution.

There should be a general solution such as rearrangement at compile time and dependency tracking at run-time.  Note that some kind of ru-time is inevitable because of separate compilation and/or irreducible expressions.

> 
> Many interval coders are accustomed to
>    double mag( interval X ); // or magnitude := max abs(X)
>    double mig( interval X ); // or mignitude := min abs(X),
> where "abs(X)" is the interval abs as I imagine you'd specify it.

We have a "little list" but the functions are not part of <cmath>, which was the subject the proposal team wanted addressed.  I attached a list of examples to this message for the benefit of those interested.

> 
> Q7. Function forms of operators: Hooray!  Then the
> C++ interval is (nearly) a C interval library plus a C++
> wrapper class?

Yes.  There are still template and overloading problems that require a set of adapter declarations, but the layer we implemented is quite thin.

> Then I can use it if I am restricted to C, for some reason.

Or FORTRAN.

>  Or is that an empty opportunity?

In terms of new code the opportunity is probably not large for general applications.  For embedded applications where reliability is very highly prized, we believe there will be substantial demand.

And in terms of maintaining and enhancing existing sofware the opportunity is quite large.

> 
> I appreciate you suggesting that implementations are not
> too hard.  In addition, we should note there are at least a
> couple quite good (tight) implementations of most of the
> common elementary functions, more evidence that a
> vendor's barrier to entry is not high.

We do not have information on the effort required to produce sharp implementations.  But ours is designed for extreme portability, complete consistency (which blunts some results), and maximum rigor with little or no concern for performance.  We expect fast/tight implementations on specific plaforms to be about the same level of difficulty.

> My reservation is that by putting more advanced tools
> (your twin functions) in the hands of people inexperienced
> with interval algorithms, you provide more opportunities
> for screwing up :-)

Other than the multiplication of entities, part of which is mitigated by a simple naming convention, how do twin functions pose a risk?

We have the expectation (based on a small sample of users) that they solve the problem of user frustration with very wide results leading to abandonment of the interval forms.  For example, a user who gets what he considers silly results, such as interval::f() returning [-inf +inf], is tempted to revert to using std::f() because he has no interval alternative that gives him an answer he considers useful.  That is the threat the twin functions tend to counter.

-- Lee Winter
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/x-tar
Size: 4687 bytes
Desc: not available
Url : http://compgeom.poly.edu/pipermail/std-interval/attachments/20060605/c95ad738/attachment-0001.tar