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

Re: Potential well and decorations

Vincent Lefevre wrote:

On 2011-07-07 09:02:20 -0500, Nate Hayes wrote:

Dominique Lohez wrote:
>Ralph Baker Kearfott a écrit :
>>On 07/04/2011 12:51 PM, Nate Hayes wrote:
>>>Dominique Lohez wrote:
>>>>Nate Hayes a écrit :
>>>>>If for example we have the interval extension
>>>>>
>>>>>P(X) = U(X) \union V(X)
>>>>>
>>>>>with
>>>>>
>>>>>U(X) = sqrt((|X| \intersect [roundDown(sqrt(a)),+Inf])^2-a)
>>>>>V(X) = -sqrt(a-(|X| \intersect [0,roundUp(a)]))
>>>>>
>>
>>If I encountered a function like Dan's, that is,
>>
>>if (abs(x) > sqrt(a))
>>    y = sqrt(x^2-a);
>>else
>>    y = - sqrt(a-x^2);
>>end

[...]

One thing I notice is if at Level 2 the function is implemented:

   U(X) = sqrt((|X| \intersect [roundUp(sqrt(a)),+Inf])^2-a)
   V(X) = -sqrt(a-(|X| \intersect [0,roundDown(sqrt(a))])^2)

so that there is a 1 ULP gap between the domains of U(X) and V(X) at
sqrt(a), then P(X) always gives a valid range enclosure and "continuous"
decoration whenever sqrt(a) is an element of |X|.

The reason this works is because the potential function is monotonic and
continuous over the Level 2 interval
[roundDown(sqrt(a)),roundUp(sqrt(a))],
and any Level 2 |X| containing sqrt(a) will be a superset of this
interval.

However, this trick doesn't seem to work for implicit data types with
dynamic precision, e.g., MPFR etc.


Anyway this works only in a particular case. For instance, if a is not
representable exactly by a FP number (or not known exactly), it will
be represented by an interval, and this tricks no longer works in such
a case.


I think as long as:
   -- there is only a 1 ULP gap on the domain between U and V at Level 2
   -- that P(X) is monotonic and continuous on that gap
it may still work.

For example, if sqrt(a) is not exactly representable by a FP number but the
interval [A_1,A_2] is the narrowest (non-degenerate) Level 2 interval such
that nextup(A_1) = A_2 and sqrt(a) is an element of [A_1,A_2], and P(X) is
implemented:

   U(X) = sqrt((|X| \intersect [A_2,+Inf])^2-aa)
   V(X) = -sqrt(aa-(|X| \intersect [0,A_1])^2)

where aa is also the narrowest Level 2 interval containing a.

Then any Level 1 number that is an element of [A_1,A_2] will at Level 2 be
contained in this interval; so the intersections in U and V will both be
nonempty at Level 2 and the union of the ranges of U and V will form a valid
enclosure of the underlying point function.



Moreover you can still extend the trick to dynamic precision (as long
as you can entirely control the precision, but this is possible with
MPFR). I mean, the problem is not whether a data type is implicit or
not, but whether the precision can be controlled.


Yes.

Nate



--
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 / Arénaire project (LIP, ENS-Lyon)