Nate Hayes wrote:
John Pryce wrote:
I do not expect this scheme to receive universal acclaim. For one thing,
it is not child's play to grasp the specifications. For another, I have
followed the Neumaier approach to the mathematics. I found this easier
to
follow than the Hayes approach which disagrees with it in various ways.
I
hope, at the implementation level it does the most important things that
Nate requires.
...I'm pleased with the progress; and I see your skill with the technical
writing continues to be a service to all of us.
You gave three interesting and important examples that help to clarify
the usage of the decorated semantics.
(i) Intersection of objects
---------------------------
> We are currently examining the application of decorations to
> Constructive
> Solid Geometry (CSG):
> http://en.wikipedia.org/wiki/Constructive_solid_geometry
> This relies heavily on the interval lattice operations min and max. For
> example, a solid object may be represented by an implicit function f.
Then
> the set of all f < 0 is inside the object, f > 0 is outside the
object, and
> f = 0 are points on the surface of the solid object. If A and B are two
> solid objects and fA and fB are their respective implicit functions,
> then
> the intersection between A and B is defined
> A intersect B = max(fA,fB)
> and the union between A and B is defined by
> A union B = min(fA,fB).
Here
A = {x | A(x)<=0},
B = {x | B(x)<=0},
where A(x), B(x) are arithmetic expressions, and an inequality is
supposed to be false if a subexpression is undefined.
We want to deduce information about
C := A intersect B,
D := A union B.
Since
C = {x | C(x)<=0}, where C(x)=max(A(x),B(x)),
D = {x | D(x)<=0}, where D(x)=min(A(x),B(x)),
this can be handled by ordinary interval evaluation of arithmetic
expressions, using min and max as binary arithmetic operations as in the
Level 1 text draft. We just evaluate the interval extension and at the
end check the decorated range enclosure.
No change in the semantics is needed, no false conclusions are generated
by the algorithm for deciding whether a box xx is inside or outside C or
D, or whether no decision is possible.
Date: Wed, 25 May 2011 17:06:12 +0200
From: Dominique Lohez <dominique.lohez@xxxxxxx>
To: "Corliss, George" <george.corliss@xxxxxxxxxxxxx>
CC: "<stds-1788@xxxxxxxxxxxxxxxxx>" <stds-1788@xxxxxxxxxxxxxxxxx>
Subject: Re: What is your philosophy? Tracking or Static?
Dominique is correct in that we often choose examples
which are mathematically difficult when perhaps some
simpler example would suffice for this argument.
Very well, let me see if I can come up with one off
the top of my head.
f(x,y,z) = max(x,y,z)
Now, max() is basically a selection function. It is
formally equivalent to:
max(x,y) = if x < y then y else x
Therefore, it takes on the properties of the selected
thing no matter what happened to the unselected thing.
Indeed, code like:
if x < 0 then sqrt(-x) else sqrt(x)
DEPENDS on the not taken path having no effect on the
taken path.
Therefore, I argue that the result of max() should be
decorated with the selected thing (or things, in the
case of overlapping intervals) & discard the unselected
items.
So, what is the answer to f(sqrt([-2,-1]),sqrt([-1,1]),
sqrt([4,9]))?
The intermediate result is max({empty,undefined},
{[0,1],discontinuous},{[2,3],defined&continuous}).
The tracking philosophy would have us return {[2,3],
undefined}. The static philosophy would have us return
{[2,3],defined&continuous}.
Which is more imformative? The one that correctly tells
us that SOME calculation was undefined even though it did
not participate in the final result? Or the one that WAS
the final result?
Note that the answer is NOT a slam dunk. It COULD be that
one of the unselected answers WAS unselected due to a bug
in the code as easily as because the programmer always
intended that it not be selected. Tracking warns us of
both the bug & the false positive. Static ignores both.
So it requires some thought to decide which is best.
What do you think?
Dan
George,
IMHO your examples are not illustrative of argument in favor of some
philosophy.
They show how problems must be reformulated when interval arithmetic is
aimed
Corliss, George a écrit :
> Dan,
>
> Thank you for the useful characterization. I, too, began assuming
> tracking, but I am coming more to the static view.
>
> Early in AD, a frequently cited difficulty was scaling:
>
> x is a vector
> s = max(|x|)
> x = x / s // Normalize
> y = lots of computations
> y = y * s // Rescale back
>
> Is y a differentiable function of x? AD is forced to assume not.
> Intervals can help decide this question more precisely, but the analogy
> is whether we care about the history or only the result.
>
When x is replaced with a box X, the scaling factor must be calculated
for the box as a whole, so it a constant for all the vector in the box.
So the problematic dependence of s with a particular vector is removed.
> Or, suppose
> x is a scalar
> f(x) = sign(x)
> y = 0 * f(x)
>
> Is y a continuous function of x?
>
This problem is ill-posed.
The interval arithmetic provide a correct enclosure of the exact result.
Since sign is discontinuous , the continuity is definitely lost for
future calculation
exactly in the same way a the result of a interval arithmetic
calculation may provide a heavy overestimation of the the exact result.
The rule must be
the system must not lie
Nothing more.
Best regards,
Dominique
> I am becoming a static-ist.
>
> George
>
> On May 25, 2011, at 6:17 AM, Dan Zuras Intervals wrote:
>
>
>>> Date: Tue, 24 May 2011 19:05:38 -0500
>>> From: Ralph Baker Kearfott <rbk@xxxxxxxxxxxx>
>>> To: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
>>> CC: John Pryce <j.d.pryce@xxxxxxxxxxxx>,
>>> stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>>> Subject: Re: Ar we succeeding?
>>>
>>> All,
>>>
>>> Does someone else also have an opinion concerning this (please)?
>>>
>>> Baker
>>>
>>>
>> Baker, et al,
>>
>> I find I do have an opinion on this. And as long as Nate's
>> motion is in its discussion period, now is as good a time
>> as any to discuss it.
>>
>> Let me put it in the form of a question I put to Nate:
>>
>> Is your philosophy about decorations a tracking approach or
>> a static approach?
>>
>> There seem to be two schools of thought about the meaning
>> of decorations.
>>
>> There is the TRACKING school in which decorations are the
>> maximal (most pessimistic) result of the tree of evaluations
>> that led up to the result to which they are attached. That
>> is, every exceptional or noteworthy incident in that tree is
>> recorded for all to see whether it is relevant to the final
>> result or not.
>>
>> Then there is the STATIC school in which decorations are
>> information concerning the current result only. Earlier
>> decorations may pass through to this result if they still
>> apply & may be discarded if they do not. In this case the
>> decoration must be able to be interpreted in the context
>> of the final result whatever happened before.
>>
>> (In either school, the decoration must be ordered WRT to
>> subsets of arguments. I believe this is both necessary &
>> sufficient for an FTDIA to be proved.)
>>
>> I asked this question of Nate because his motion seemed to
>> be primarily of the tracking school but with some static
>> features thrown in.
>>
>> I think we need to be consistent on this point. As much
>> for our own understanding as to explain the meaning of
>> decorations to the rest of the world.
>>
>> I will admit that I started out in the Tracking school.
>> But some remarks I've heard in this forum & privately have
>> suggested to me that the Static school might serve us better
>> as a standard.
>>
>> So I ask of all of you: Which philosophy should we espouse?
>> Tracking or Static?
>>
>> I believe that once we decide this many of our more
>> difficult questions will fall out as obvious.
>>
>> Yours,
>>
>> Dan
>>
>
> Dr. George F. Corliss
> Electrical and Computer Engineering
> Marquette University
> P.O. Box 1881
> 1515 W. Wisconsin Ave
> Milwaukee WI 53201-1881 USA
> 414-288-6599; GasDay: 288-4400; Fax 288-5579
> George.Corliss@xxxxxxxxxxxxx
> www.eng.mu.edu/corlissg
>
>
>
--
Dr Dominique LOHEZ
ISEN
41, Bd Vauban
F59046 LILLE
France
Phone : +33 (0)3 20 30 40 71
Email: Dominique.Lohez@xxxxxxx