RE: [boost] Formal Review for Interval Library beginning

From: Guillaume Melquiond (gmelquio_at_[hidden])
Date: 2002-09-04 02:27:34

On Tue, 3 Sep 2002, Rozental, Gennadiy wrote:

> > I was working in the same domain for some time. Interval arithmetic doe=
> s is
> > very useful here. Note though that in most cases we need more generic
> > abstraction - ordered list of intervals possibly open or half open.
> 
> > Thanks Gennadiy for confirming my suspicion. If you want half-open
> > intervals, though, a range library would be more suited than an interval
> arithmetic library. 
> > We cannot (and will not) represent all kinds of intervals. This would
> unnecessarily burden the library, and for most
> > users it  would not represent a benefit.
> 
> IMO plain interval would not be enough in many domains, not only static
> analysis. Let say you want to represent the results of solving multiple
> inequations. 
> You immediately face the need for this kind of more generic abstraction. Or
> area of definition for variable. Even more simple example: How you going to
> represent result of operation 1/x where x = [-1, 1]?
>    From what I view, without such generalization the library will have much
> more limited usability.

In your example, there were some intervals with open bounds (is it the
correct expression?) and I'm not sure to understand if you expect the
library to provide them or not? If your generalization was only about
interval lists, please forget the next paragraph.

The library manipulates interval with closed bounds. But it doesn't mean
that it is not usable for intervals with open bounds; it's just a matter
of correctly choosing the base number type. Here is an example:

  struct a_bound {
    bool is_included;
    T the_number;
  };

  struct my_rounding_policy {
    a_bound add_down(const a_bound& x, const a_bound& y) {
      a_bound result;
      bool is_exact = do_add(&result.the_number, x, y, ROUND_DOWN);
      result.is_included = x.is_included && y.is_included && is_exact;
      return result;
    }
  };

I only described one half of the addition in this example. But I hope it's
clear that it can be extended to the other operations and that it
correctly defines arithmetic operations on interval whose bounds are not
always included.

Please note that the do_add function is not some hazy concept:
multi-precision libraries (MPFR for example) usually define it; and on
IEEE-754-compliant floating-point units, it's just the plain old addition
followed by a test of the status register.

I won't describe the comparisons for such intervals since comparison
policy actually is one of the hot topics of the review and I don't want to
add fuel to the fire.

> > IMHO, this is the topic for another library on top of the interval
> > library. As much as I would like to solve the world's greatest problems,
> > I have to draw a circle and work within.
> 
> I think it just one small step ahead in terms of generalization. In most
> cases it does not require too much efforts. Instead of operation over pair
> you will operate over list of pair. There are some specific challenges of
> course. Like we will need intersection, union and difference. But it should
> be pretty strait forward also. You current interval will became just a
> particular case for more abstract implementation.

You're right; instead of operation over pair, it will operate over list of
pair. So let's see an example. Let's take the addition, it's quite an
easy operation. How do we do the addition of two lists of interval? Here
is an algorithm:

  X and Y are the input lists
  let R be the resulting list
  for each interval i in the list X do
    for each interval j in the list Y do
      let k be the result of the interval addition of i and j
      for each interval m in the list R do
        if m and k overlap then
          replace, in the list R, m by hull(m,k)
          break
        endif
      done
      if we didn't find any overlap then
        append m to the list R
      endif
    done
  done

Now, the addition works on interval lists. But it's too bad, the
temporal complexity is terrible: yes, it's an algorithm in O(n^4). Unless
you are not interested at all in the performance of your program, it is
quite unacceptable.

So let's do better. The first idea could be to use sorted lists. Since the
addition is a monotonic operation in each of its argument, we can adapt
the merge-sort algorithm to our case. The temporal complexity will be
better but unfortunately it will involves a lot of complex memory
operations. So maybe there was another way to do it: heap, trees, balanced
trees, red-black trees? (And all of that is quite limited, why not even
use directed acyclic graph with intersection, union and difference nodes?)

I won't describe all the available possibilities and write the various
algorithms. And it was just for the addition. What will we do with the
multiplication and the division which are not monotonic on their whole
domain but only on smaller parts? And the transcendental functions?

Yes, you were right, the library can be generalized to deal with lists of
intervals. But are you still ready to maintain that it is "just one small
step ahead in terms of generalization" and that "it does not require too
much efforts"?

Regards,

Guillaume