[boost] Re: Proposal: Interval arithmetic library

From: Gavin Collings (gcollings_at_[hidden])
Date: 2000-03-06 06:38:57

> > have you considered abandoning the class invariant low <= up in
favour
> > of an approach where there are no constraints upon the individual
> > bounds.  Reason: sometimes it's useful to distinguish a +/- from a
-/+
> 
> This would introduce a lot more freedom into the definition
> of the operators, i.e. you would have to state for each
> operator if you wanted [low, up] or [up, low] for the result,
> of course depending on the input. I cannot see any mathematical
> definition for that which is as nice and concise as the one
> currently in use (i.e. the invariant low <= up together with
> I = op(I1) => for all x in I1: op(x) in I).

I've thought about this a bit more.  The trigger that formed the
thought in my head was the division operator with its special meaning
for identical objects giving a result of 1.0 to machine precision.  My
thinking was that this was a special case of handling correlations
between the errors - i.e. special use is made of the fact that when the
dividend is at the top of its range, then so is the divisor.  I
wondered if this could be generalized.  The idea would be to allow
users to enter the interval in the way they choose to reflect what they
know about parity correlations between input error terms and just let
them propogate.  Taking multiplication (a*b) as an example, the normal
case of same parity would be handled as if

   result.hi = a.hi * b.hi
   result.lo = a.lo * b.lo

A simple implementation would allow the user to enter reverse ranges
for reverse correlated terms.  So the reverse correlated case for b
would be as if

   result.hi = a.hi * b.lo
   result.lo = a.lo * b.hi

You could break the current invariant with this type of thing, but that
contains some of the extra information in the output term.

However, this simple implementation would not handle the case that
provoked me.  Namely a/(1 * a) being different from a/a.  Of course,
the reason is that while reversing the bounds for multiplication
implements the reverse correlation, it is not so simple for division
since the combination of terms is reversed.  In general, as you point
out, there are many ways in which the inputs can be combined.

So, OK, instead of simply reversing the order of terms to reflect
correlation (too simple), lets have a flag, derived from a constructor
argument, stating how the term is correlated with others -
uncorrelated, forward correlated or reverse.  And determine some
propogation rules, while retaining the class invariant.

I may be missing something but this seems to get us most of the way
there (?).

A more general implementation would allow terms in expressions to
somehow register their interest in particular sub-correlation(s) and
have those correlations propogated through sub-expressions.  It could
be done, but may not be worth it.

I'm conscious that I may be way past the line drawn between pragmatic
implementation and over-design.  My feeling, though, is that the
interval class should have a coherent policy on this issue, even if it
is explicitly to do nothing.  So while I would (gratefully) accept a
class with no correlation handling, I'm a little uncomfortable that
they may be creeping in through the back door; specifically the special
case for a/a.  Should this really give a different answer to a/(1 * a)?
 After all not everyone manages to cancel all terms in algabraic
expressions before putting them into code.

Gavin.