[std-interval] More on interval computations as proofs

[Guillaume Melquiond]

Le vendredi 06 octobre 2006 à 07:13 -0500, R. Baker Kearfott a écrit :
> Certainly, it is desirable that sqr(x) return [0,1] for x=[-1,1]. 
> However, isn't the question of x*x returning [0,1] instead of [-1,1]
> a question of optimization, and of proper interpretation of what
> the programmer intended?  Also, have we distinguished what should
> be mandated in the standard and what is just desirable in an
> implementation?

So that there is no misunderstanding, I was speaking of the expression
x*x as a mathematical expression. So its range is [0,1] on the domain
[-1,1]. This is different from the C++ expression x*x with "interval
x(-1,1);". It has to return a superset of [-1,1]. I don't expect any
optimization here as x is meant as a set of real numbers and not as a
mathematical expression. Two identical sets do not necessarily bound the
same mathematical expression.

I can even imagine situations where optimizing x*x to sqr(x) could be
dangerous at execution-time. This is a bit far-fetched, but let's
imagine an application which uses a cache to store the intervals a user
entered as variable ranges. The user types "[-1;1]" as a range for both
variables "a" and "b", so the pointers range["a"] and range["b"] both
point to the same interval in the cache. Now the user asks for the
product of "a" and "b". As a consequence, the C++ program will execute
something close to (*range["a"]) * (*range["b"]). As the pointers are
the same, we are looking at a "x*x" situation, yet we really don't want
the result to be [0,1].

So I don't think it is desirable for an implementation to mess with the
evaluation rules of intervals. Expression manipulation should be
implemented through another datatype, so that the semantic of intervals
is not perturbed. For example, people could write a "bounded_expr" class
that would be implemented on top of "interval" and that would provide
the semantic of mathematical expressions (x-x = 0 and the like); it
could rely on Taylor models to compute tight bounds. But this is way out
of the scope of this proposal.

Best regards,

Guillaume