Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Version 2.11, Proposal for interval standardization

Arnold Neumaier wrote:

Sylvain Pion schrieb:

Arnold Neumaier wrote:

Sylvain,


- I find it strange to mention "standard intervals" and "non standard intervals".


The reason is that I want nonstandard intervals to be supported in a
minimal way that enables someone interested to create a
standard-complying implementation of Kahan or Kaucher arithmetic.


I understand.
I was just hoping that there could be a more minimal approach to this :)


- 1.5.6 : anyInterval(l,u) : what happens if e.g. l>u ?
 Should some "undefined behavior" notion be defined somewhere and used here?


Nothing special happens. This is the difference between 1.5.5 and 1.5.6.


I noticed the difference, but still: what happens if I do it?
Is an implementation allowed to stop the program and issue an error
(in debug mode, for example)?
In the C++ standard, this would typically be phrased by referring to
undefined behavior.


The behavior of anyInterval(l,u) is fully defined.
This function is needed to be able to do something useful with nonstandard intervals, should someone care to
implement Kaucher arithmetic, say. 

I see that now.  Thanks.


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.

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... (?)

Or what am I missing?


Mention would be needed only if it affected some other operation.



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.
My proposal also removes the need to define text for constant expressions
as it removes section 2.6.

Anyway, if you don't feel like adding it to your draft now, it can be
proposed again later.


I don't want to specify anything for that.

The transformation (1/interval(3))*3   ->  interval(3) is covered since
in 2.6., only requirements on the results are specified, not on the means how to obtain them. 

Yes, but I was suggesting to remove section 2.6, by generalizing it with what
I just proposed, hence the example that shows that it applies to constants
as well, just like your current section 2.6.

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature