Re: Comments on decoration ill, intersection and union
On 2012-12-03 11:15:32 -0600, Nathan T. Hayes wrote:
> Using the min rule to perform a lengthy computation returns a decoration
> EIN, DAC, DEF, TRV or EMP with the following meaning (I use UPPERCASE to
> distinguish a decoration computed by lengthy computation/propagation as
> opposed to lowercase to distinguish the mathematically true decoration of
> any (f,xx) pair):
>
> Result The mathematically true decoration of (f,xx) is:
> EIN => ein
> DAC => ein or dac
> DEF => ein or dac or def
> TRV => ein or dac or def or emp
> EMP => ein or emp
So, if it happens that you have an empty input, the decorations
won't give any information; by that I mean that whatever the result
you get, there's still the possibility that the input is empty.
However this can be fine if you take the interval part into account.
For instance,
(Empty,ein) + ([1,1],dac)
would yield (Empty,dac) with the min-rule. But a dac function with
an empty result necessarily means that the input was empty.
I wonder whether the result EIN is useful in practice on arithmetic
operations, since it will quickly disappear, unless the implementation
optimizes the result to increase the decoration when it can deduce
that the input is empty (like on the above example). This would make
the ein decoration purely virtual (i.e. instead of adding an ein
decoration, it would be sufficient to modify dac and def to include
the "empty input" case).
> > > This allows set-theoretic operations like intersection and union to be
> > > decorated. For example, the function in Example 2 on pp. 34-35 may be
> > > implemented:
> > > U = f1(X intersect [-oo,-2])
> > > V = f2(X intersect [-2,2])
> > > W = f1(X intersect [2,+oo])
> > > return U union V union W
> >
> > X is the input. If it is not empty, you'll never get ein in the
> > propagations, unless you have special rules for ein.
>
> If X is Empty, the result is (Empty,DAC), since, for example:
> U = f1((Empty,ein) intersect ([-oo,-2],dac))
> = f1((Empty,DAC))
> = (Empty,DAC)
But what if only the intersection is empty, say if X = [0,1]?
([0,1],dac) intersect ([-oo,-2],dac) = (Empty,DAC)
though the input X is *not* empty. So, DAC is meaningless:
* The true decoration cannot be ein because the input is not empty.
* The true decoration cannot be dac because a dac function over a
non-empty interval cannot have an empty result.
So, whether with the proposed decoration system or with yours, if
you want decorations on intersect and union results, this needs
special care to say what it means, the risk being that if intersect
(or union) is used in some other context, the final result could be
wrong.
> Note that under the current proposal without EIN, if intersection
> and union operations propagate decorations the result for any
> nonempty X would be a nonempty interval with an EMP decoration.
Your decoration scheme has some form of opposite problem, as seen
above.
--
Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)