Re: Version 2.11, Proposal for interval standardization
Sylvain Pion schrieb:
Arnold Neumaier wrote:
Sylvain Pion schrieb:
Arnold Neumaier wrote:
Sylvain,
This is a good thing, but I think we can generalize
it to any kind of sub-expression, not only those exact
"constant" expressions.
The idea is that we should allow an implementation to produces
tighter results
for combined operations when it can do so. For example, it
should be possible
to turn the function "(x/7)*7" into "x", or turn "sqrt(x*x)"
into "abs(x)",
since these transformations produce proovably tighter intervals
compared
to the step-by-step evaluation, and the containment guarantees
are still
there for the whole function.
Unless I miss some arguments which would make these
transformations invalid
for some applications, I think that we should mention it,
otherwise we may
prevent some optimization opportunities.
This is difficult to specify in a standard, since the list of useful
transformations is difficult to establish, and the demands placed on
the
implementor is significantly increased. Moreover, sometimes, different
equivalent formulations have different advantages, so that there will
be hardly an agreement of what to demand. Such things are better
handled
in a context like automatic differentiation type software, which
requires different expertise than those have who are likely to create
a good interval implementation.
We must place a limit to what to include in the standard.
My recommendation is of course my personal judgment, but I tried
to put the border where it benefits most.
Maybe I was not clear enough. I am not suggesting that the standard
should
*require* those transformations, I am suggesting that it *allows* them.
And this is currently not the case in your proposal, except in this
paragraph,
which sounds strange to me, hence my suggestion to generalize it.
Nothing forbids providing additional functionality beyond that
specified by the standard. Thus it is automatically allowed.
Well, I *think* it is indirectly, but explicitly forbidden in your
current proposal, and that's the whole point. The reason I think
so is that in your proposal, functions are defined in isolation,
and at best they each return the "tightest" accuracy, and the refer
only to their arguments. So, if x=[1,1], evaluating x/[3,3] *must*
return an interval y which is the tightest result and not a singleton,
and y*[3,3] then *must* return the tightest of this, which is not
a singleton. So the transformation to [1,1] is not allowed.
The standard is supposed to define interval arithmetic on machines,
not what people can do with it.
Thus we specify single operations, but not how they may be combined, and
under which conditions better results are obtained. This is a matter of
theory on interval methods, not of a standard.
Theory tells (or does not tell) what gives best results in
infinite-precision interval arithmetic; the standard guarantees that
if you program this using a standard-conforming implermentation, you'll
get correct enclosures of the theoretical result.
A programming system with elaborate syntax transformation capabilities
can implement some or all of the theory - but then it must still call
routines that do the elementary operations. How to do these (and only
that) must be specified by the standard.
Moreover, if that was already allowed, it would automatically apply
to constants, and then you would probably not have felt the need
to add section 2.6 either... (?)
The point is that many compilers do constant folding at compile time,
while they cannot fold variables. Thus the user should have a way to
pass a constant that is to be accurate as a string.
In constraint programming, constants behave differently than variables,
so tight enclosures for the latter are a benefit.
My suggestion is to remove the special case of those constant
expressions
(which in fact only *allows* shaper intervals in this case), and replace
it by a general authorization for the implementation to perform any such
transformation. This could be phrased, I think, without any explicit
list
of transformations (which I agree would not be realistic).
I can suggest the following wording:
For any expression combining functions over a set of input intervals,
an implementation is allowed to return a shaper interval than the one
required by the involved functions taken separately, provided that the
containment property is still ensured for the result of the expression,
for all possible real values in the input intervals.
Examples of valid such transformations:
- (1/interval(3))*3 -> interval(3)
- (x/2)*2 -> x
- sqrt(square(x)) -> abs(x)
This would require talking about text containing variables.
I don't think so: I was not referring to text, I was referring to
expressions,
which are compositions of functions, basically.
The standard is supposed to be language-independent.
But expressions are usually parsed by the compiler, and are no
longer available in a language-independent form, unless passed as text.
Arnold Neumaier