[std-interval] Re: Std-interval Digest, Vol 5, Issue 5
Ray Moore
rmoore17 at columbus.rr.com
Mon Jun 5 11:15:13 PDT 2006
John and George,
Thanks for the link to your paper "Interval arithmetic with containment
sets" (2006), submitted to Computing.
It is a fine effort. I think you are on the right track with containment
sets.
Good luck with the ISL Project !
Ray Moore
----- Original Message -----
From: <std-interval-request at compgeom.poly.edu>
To: <std-interval at compgeom.poly.edu>
Sent: Monday, June 05, 2006 6:04 AM
Subject: Std-interval Digest, Vol 5, Issue 5
> Send Std-interval mailing list submissions to
> std-interval at compgeom.poly.edu
>
> To subscribe or unsubscribe via the World Wide Web, visit
> http://compgeom.poly.edu/mailman/listinfo/std-interval
> or, via email, send a message with subject or body 'help' to
> std-interval-request at compgeom.poly.edu
>
> You can reach the person managing the list at
> std-interval-owner at compgeom.poly.edu
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of Std-interval digest..."
>
>
> Today's Topics:
>
> 1. Re: list of functions for intervals (George Corliss)
> 2. Re: Interval comparison operators (Dr John Pryce)
> 3. Re: extra functions for intervals (first.i.last at comcast.net)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Sun, 04 Jun 2006 20:40:04 -0500
> From: George Corliss <George.Corliss at marquette.edu>
> Subject: Re: [std-interval] list of functions for intervals
> To: For discussions concerning the C++ standardization of intervals
> <std-interval at compgeom.poly.edu>
> Cc: ISL List <isl at interval.louisiana.edu>
> Message-ID: <C0A8F5A4.9C0%George.Corliss at Marquette.edu>
> Content-Type: text/plain; charset="US-ASCII"
>
> Lee and all,
>
> Excellent. I like your proposal better than mine, but (of course?) I have
> some questions for you and the list. I had in mind a minimalist standard;
> you are more ambitious. If we can summon support for an ambitious
> standard,
> LET'S DO IT.
>
>
> 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?
>
> 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. 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.
>
> Q3, par. 7. "existence of a type designed to hold multiple instances of
> values" Such a type could improve the practicality of our cset proposal,
> too. Thank you!
>
> Q4, par. 9. "wrong" and "nacceptably wide"
> --> "wrong" and "unacceptably wide"
>
>
> 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. 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. 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>.
>
> Q6. Additions?
> interval square( interval X )?
>
> 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.
>
> Q7. Function forms of operators: Hooray! Then the C++ interval is
> (nearly)
> a C interval library plus a C++ wrapper class? Then I can use it if I am
> restricted to C, for some reason. Or is that an empty opportunity?
>
> 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.
>
> 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 :-)
>
> (In preparing this response, I have consulted on some, but not all, of
> these
> points with John Pryce, R. Baker Kearfott, Ned Nedialkov, and Spencer
> Smith.)
>
> Dr. George Corliss
> Electrical and Computer Engineering
> Marquette University
> P.O. Box 1881
> 1515 W. Wisconsin Ave.
> Milwaukee, WI 53201-1881
> George.Corliss at Marquette.edu
> 414-288-6599 (office); 288-4400 (GasDay);
> 288-6280 (Dept.); 288-5579 (fax)
> Office: Haggerty Engineering 296
> Www.eng.mu.edu/corlissg
>
>
> On 6/3/06 7:30 PM, "first.i.last at comcast.net" <first.i.last at comcast.net>
> wrote:
>
>> -------------- Original message ----------------------
>> From: Sylvain Pion <Sylvain.Pion at sophia.inria.fr>
>>> Dear all,
>>>
>>> We have been thinking about the list of floating-point functions
>>> which we could propose an interval version for.
>>> More precisely, we have looked at the current list of floating-point
>>> functions from the latest draft of C++0x
>>
>> [...]
>>
>>> What do you think of these lists ?
>>> Is something important excluded ?
>>> Is there anything that should be excluded ?
>>>
>>> Note that existing implementations do not necessarily offer all
>>> proposed functions, so any comment on the implementation
>>> difficulty (for interval<float>, interval<double> and
>>> interval<long double>) would be appreciated.
>>
>> Attached is a file containing comments on the issues you raised and
>> suggested
>> specifications for many of the functions at issue. Having studied this
>> issue
>> in great detail, implemented all of the <cmath> functions, and designed
>> implementations of the c99 functions I can assure you that the
>> implementation
>> of the interval versions of the <cmath> functions, including disjoint
>> results,
>> is quite reasonable.
>>
>> Using typical elementary functions as a benchmark (trig, hyperbolics, and
>> exponentials) all but two of the c99 functions require similar or lesser
>> implementation effort. We are still studying the recalcitrant pair of
>> functions, beta() and ellint_1(), with an eye to efficient and robust
>> implementation.
>>
>> The attached document is a summary aimed at raising issues and
>> identifying
>> areas meriting additional discussion rather than a comprehensive
>> specification
>> with endless detail but no rationale. Therefore readers who are only
>> concerned with concrete suggestions should not read it.
>>
>> -- Lee Winter
>> _______________________________________________
>> Std-interval mailing list
>> Std-interval at compgeom.poly.edu
>> http://compgeom.poly.edu/mailman/listinfo/std-interval
>
>
>
> ------------------------------
>
> Message: 2
> Date: Sun, 04 Jun 2006 23:04:43 +0100
> From: Dr John Pryce <j.d.pryce at ntlworld.com>
> Subject: Re: [std-interval] Interval comparison operators
> To: For discussions concerning the C++ standardization of intervals
> <std-interval at compgeom.poly.edu>, "R. Baker Kearfott"
> <rbk at louisiana.edu>
> Message-ID: <6.2.5.6.0.20060604213551.02ecd4f0 at ntlworld.com>
> Content-Type: text/plain; charset="us-ascii"; format=flowed
>
> Lee, and participants in this group
>
> At 19:12 04/06/06, R. Baker Kearfott wrote:
>>My view is that, if there is a hopeless lack of consensus, it may
>>indicate that there isn't a single "right" way, but choosing
>>a particular way and having a standard is better than having none.
>>However, we should strive to maximize the utility of the language
>>in the standard.
>
> Like Baker, I feel optimistic that a consensus will emerge. I
> STRONGLY agree with Baker's paragraph above.
>
> Lee, you have written eloquently of the Principal Value (PV) model
> that you have been working on. If it is as different in
> concept/philosophy/goals (I don't know enough about it to know which
> of those words are most appropriate) from the "classical interval
> model" as you say, then certainly it needs a different standard from
> one that supports the classical model. Therefore, I do not see you as
> in conflict with the classical intervallers, but as complementary.
>
> However I speak as the principal author of containment set (cset)
> theory for the last few years. Csets are NOT the most widely held
> view of classical intervals, and when I started working on them for
> Bill Walster under contract to Sun around 2001 they were generally
> seen as an eccentricity that would soon die out.
>
> Evaluation of cset theory by the interval community was delayed
> slightly by commercial confidentiality. That prohibited putting some
> aspects of csets in the public domain - mainly Sun's implementation
> detail. The main reason for delay was that Bill and I had serious
> disagreement, not over what a cset-based interval implementation
> should do, but about what the results *meant*. I believed, and still
> do, that Bill's philosophy of csets at that time was mathematically
> inconsistent. As a result we could not agree on a paper to submit to
> the open literature. We spoke at conferences etc, but some of the
> assertions we made were incompatible, which was not good for credibility.
>
> Maybe it was a blessing in disguise, because then I joined the ISL
> project steering committee, and working with 3 guys who have jointly
> over 50 years interval programming experience, plus a professional
> software engineer, widened my outlook so that the paper I eventually
> wrote, Pryce and Corliss "Interval arithmetic with containment sets"
> (2006), submitted to "Computing", see
> http://homepage.ntlworld.com/j.d.pryce/isloct05/IntvlArithCsets.pdf
> was far clearer and more concise than it would otherwise have been.
>
> And, to my surprise, my ISL colleagues decided of their own accord
> that a cset-based interval system was the one they preferred, though
> the well-known packages they had up to then used, and in one case
> written, were based on what I call the Simple System.
>
> How did this come about? I believe it was because I had been able to
> write an account that showed such a system is
> - rock-solid mathematically,
> - actually useful.
>
> Both are necessary conditions for acceptance in this corner of
> scientific computing (sadly, not sufficient). I urge you to move the
> task of writing up what PV intervals are all about to near the top of
> your priorities, if not the actual top. And get it into the open
> literature so that people can pull your ideas to pieces (as my cset
> ideas have been for several years), force you to refine them, and
> eventually be convinced you are making sense.
>
> I find many things you write very weird or downright false (e.g.
> distinctions between line segments and sets, and tests on the empty
> set). That is because I am matching it against my model, which is
> firmly based on classical set theory. You have work to do to convince
> me, but my mind is open. As I am a mathematician, the "rock-solid
> mathematically" interests me more, initially, than the "actually
> useful". I think many people with more interval experience and/or
> more influence in the scientific world than I would agree with me.
>
> PV intervals must be mathematically consistent, or they will die. But
> there is more than that. You must have an underlying purpose for
> them, or philosophy about them, that explains why this consistent bit
> of mathematics actually helps humans solve real life problems. From
> what you write, you are a fair way towards having both, but you won't
> convince the world unless you WRITE IT UP for public evaluation.
>
> Best wishes for that project.
>
> John Pryce
>
>
> ------------------------------
>
> Message: 3
> Date: Mon, 05 Jun 2006 10:17:46 +0000
> From: first.i.last at comcast.net
> Subject: Re: [std-interval] extra functions for intervals
> To: For discussions concerning the C++ standardization of intervals
> <std-interval at compgeom.poly.edu>
> Message-ID:
> <060520061017.1343.448404CA0003420D0000053F22092299279B9C0E04D207D29B9C9D0700 at comcast.net>
>
> Content-Type: text/plain; charset="us-ascii"
>
> -------------- 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.tar
>
> ------------------------------
>
> _______________________________________________
> Std-interval mailing list
> Std-interval at compgeom.poly.edu
> http://compgeom.poly.edu/mailman/listinfo/std-interval
>
>
> End of Std-interval Digest, Vol 5, Issue 5
> ******************************************
>
More information about the Std-interval
mailing list