I don't think there is any conceptual difficulty in defining arithmetic on
sets of intervals, including open/closed endpoints.
The challenge is implementing them uniformly across all of Maxima's
functionality reasonably cleanly and reasonably efficiently. Several
approaches have been proposed in the past, but no one has actually
implemented any of them completely.
Any approach should generalize to other kinds of "generalized number", such
as complex numbers in rectangular form, complex numbers in polar form,
complex neighborhoods (circular, rectangular, or other), partial fractions,
quadratic numbers, etc. etc. (Most of these are closed under elementary
arithmetic, but not necessarily under other functions.) Not the specifics,
of course, but the mechanism.
-s
On Tue, Feb 12, 2013 at 1:16 PM, Henry Baker <hbaker1 at pipeline.com> wrote:
> I've looked at several issues involved in coding up my "ordered lists of
> disjoint atomic intervals" proposal.
>
> The potential integration with other portions of Maxima is quite
> significant.
>
> For example, one needs to be able to characterize many functions at the
> values MINF & INF.
>
> This system should integrate with Maxima's functionality of _limits_.
>
> For the elegant implementation of intervals, one needs the concept of
> interval "endpoints", which specify 3 things:
>
> 1. A _bound_, which may include the additional values MINF, INF;
> 2. A bit indicating whether the endpoint is _open_ or _closed_ ("(" v.
> "["; ")" v. "]"); and
> 3. A bit indicating the _direction_ of approach ("(" v. ")"; ")" v. "]").
>
> An atomic interval consists of a lower endpoint, where the direction is
> from above, and
> an upper endpoint, where the direction is from below.
>
> Thus, the interval "[0 INF)" = "[0" intersect "INF)" is the non-negative
> reals, including 0, but not +infinity,
> while "(0 INF)" = "(0" intersect "INF)" is the positive reals, not
> including 0, and not including +infinity.
>
> (Intersection itself is commutative, but the interval "INF) [0" is more
> readably printed as "[0 INF)", etc.)
>
> Mathematicians sometimes use the notation "0-" for "0)" and "0+" for "(0"
> in limits and integral bounds.
>
> We need to extend functions to be able to compute not just f(x), but also
> f("x)"), f("x]"), f("(x"), and f("[x").
>
> If f(x) is "increasing" (using Maxima terminology) and also continuous,
> then
>
> f("x)") = "f(x) )"
> f("x]") = "f(x) ]"
> f("(x") = "( f(x)"
> f("[x") = "[ f(x)"
>
> If f(x) is "decreasing" (using Maxima terminology) and also continuous,
> then
>
> f("x)") = "( f(x)"
> f("x]") = "[ f(x)"
> f("(x") = "f(x) )"
> f("[x") = "f(x) ]"
>
> In particular, we will need an AT/ATVALUE type of database for these
> extended values.
>
> Consider the function invert(x):=1/x.
>
> The domain of invert(x) is (MINF 0) union (0 INF).
>
> We would like our database to record the following facts:
>
> invert("(MINF")="0)",
> invert("0)")="(MINF"),
> invert("(0")="INF)", and
> invert("INF)")="(0".
>
> However, we cannot declare invert(x) a "decreasing" function, because
> although 1<2 and (1/1)>(1/2),
> -1<1 and invert(-1)=-1 < invert(1)=+1.
>
> But we can often gain precision in interval analysis by breaking invert(x)
> into 2 partial functions:
>
> invert_negative(x):=1/x, defined only on the domain (MINF 0); and
> invert_positive(x):=1/x, defined only on the domain (0 INF).
>
> Now, both invert_negative(x) and invert_positive(x) can be declared
> "decreasing" functions.
>
> We can now define invert(x) as:
>
> invert(x):=if x<0 then invert_negative(x) elseif x>0 then
> invert_positive(x) else error("domain error for invert()");
>
> By always "inlining"/"expanding" invert(x) as if it were a _macro_ instead
> of a function, the interval analysis can
> sometimes gain additional precision by forcing the analysis to handle
> individual cases, depending upon the sign of x.
>
> Also, now that we have characterized invert(x) on its entire domain, we no
> longer have to "special case" invert(x),
> because "decreasing" tells us everything that we need to know about
> invert_negative(x) and invert_positive(x) to be
> able to perform interval analysis.
>
> Other complicated functions -- e.g., sin(x) -- can also be broken down for
> interval analysis:
>
> sin(x):=sin_range_reduced(%pi-mod(%pi-x,2*%pi)),
>
> where the domain of sin_range_reduced(x) is (-%pi %pi], and
> sin_range_reduced(x) can be declared "increasing".
>
> *** See the Maxima manual description of mod(x,y). ***
>
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>