[std-interval] Discontinuity flag
tupper at gmail.com
Thu Oct 12 23:48:04 PDT 2006
Ron Avitzur alerted me to this discussion last week. Initially, I
wasn't going to add any comments, but I've since decided to add a few.
Guillaume Melquiond, Mon Oct 9 15:46:39 PDT 2006:
>So, if we want to use the most interesting interval algorithms, we
>should systematically use something like a pair<interval, bool> instead
>of just an interval, both at input and at output of interval functions.
>This is neither usable nor efficient.
This is the sort of thing I've done in the past. I'm not entirely sure
what is meant by "neither usable nor efficient". I combine the flags
(which I've referred to as "property tracking" in the past) and value
bounds into a data structure which can then be passed around
conveniently. Most of my libraries handle a number of flags; keeping
these together can improve efficiency (single integer operations can
set multiple flags at once). As I've written in a recent paper, flag
handling can give integer units something to do while floating-point
units hold up computation.
I haven't used exceptions for a variety of reasons, two being:
1. I don't see evaluations that interact with the flags as
exceptional. With some problems, such evaluations can be the norm
rather than the exception. Exception handling schemes are usually
designed for exceptions to be exceptional (to occur infrequently).
2. Not all of the flags I deal with are monotonic over an evaluation.
There is an arithmetic of flags. I'd have to add exception handling
code to the evaluation routines to replace what I do with flags.
Dr John Pryce, Wed Oct 4 20:26:24 PDT 2006
>At first I thought it useful to have two separate flags, one for
>defined and one for continuous, but in all the applications I have
>considered, it sufficed to check for the function being (defined AND
>continuous) on its input box. I.e. only have one flag.
Within a single library, I've done both continuity and domain tracking
in the past as (among other reasons) I've dealt with functions that
are total but not continuous. One such function is the floor (/
greatest integer) function. Inequalities can (sometimes) be decided in
the (possible) presence of discontinuities. A concrete example would
be to give GrafEq y .LT. floorx.
Another way in which continuity flags differ from domain flags can be
seen by considering multiplication by zero or application of a
locally-constant function (such as the floor function). Even though an
incoming argument is (potentially) discontinuous, the result may be
known to be continuous. (One could take a look at the floor routine
from my 2001 siggraph paper; continuity information for the result is
inferred from domain information for the argument when the argument is
known to not straddle a discontinuity.)
Dr John Pryce, Wed Oct 4 20:22:06 PDT 2006
>Wolff, I would hate to be the Engineer, who has
>successfully tested his APPFCN in floating-point
>and now has to re-write some possibly lengthy
>code putting in all these flags.
I don't see how flags / exceptions / global variables differ much
here. Is it because I bundle the property bounds (/ flags) and value
I've thought of a few other comments, but I'll limit myself to that
for now. Some more information on how I've dealt with flags is in my
M.Sc. thesis and (I think...) older interval mailing list messages
from around that time.
More information about the Std-interval