RE: [boost] Formal Review for Interval Library (was: IntervalLibraryreminder)

From: Guillaume Melquiond (gmelquio_at_[hidden])
Date: 2002-09-10 02:25:40

On Mon, 9 Sep 2002, David Bergman wrote:

> Herve,
>
> I got the impression that you have fixed your library to one-dimensional
> continuums (in C++ defined by float, double and long double).
>
> This impression stemmed from the arguments in this verification process.
> That is what I meant by you regarding the template instantiations as
> something I denote by "implementation specialization". This is why the
> requests for more generic use (traversal, partial ordered types etc.)
> went unresponded, or responded by reminders of the scienific purpose of
> this library, that it should allow for direct substiution of exact
> arguments with these intervals in arithmetic and transcendental
> operations.
>
> There is nothing wrong with that, by the way. A purely "mathematical"
> (read "operating on a linear continuum") interval is good in itself. I
> just do not want us to cheat ourselves by thinking that the interval
> abstraction could be used for other elements. And, I do not mean "being
> able to instantiate without compiler objections". I mean real use.
>
> No problem, by inserting it into "boost::numeric" the nature of the
> abstraction will be further defined, as well.
>
> To reiterate what I meant with my two categories of template
> specializations (or instantiations): (1) conceptual specialization, is
> where we get some new concept, inheriting properties from the template
> and (2) implementation specialization, is where we get the same concept,
> but with other implementation-defined characteristics. I argue that
> "interval<float>" and "interval<double>" are category-2 variants.

And interval<rational<...> > and interval<int> and interval<mpfr> and
interval<a_continuous_numeric_type> and etc?

So yes, the library deals with one-dimensional continuums. But, after all,
this library is an *interval arithmetic* library. And since the library
was designed in order to be used with any numeric type (with an arithmetic
total order), I think the library is more than just an "implementation
specialization" for 'float', 'double' and 'long double'.

The specializations really inherit properties from the template. Indeed,
all the operations on intervals are defined once and for all; they are
generic and aren't specialized.

> A lot of Boosters complain and warn other developers to not be overly
> abstract, so the pragmatic choice you made, with heavy focus on rounding
> policies is probably the right one.
>
> Regards,
>
> David

Concerning 'complex', you seem to prefer 'interval<complex>' rather than
'complex<interval>'. So, let's see, what could be an 'interval<complex>'?

The first thing which come to mind is probably to define
'interval<complex>' by a rectangle of the complex plane. And the bounds
would be the upper left corner and the lower right corner. And the order
would be the partial order that allows to do that (I would be glad to draw
a little figure, but I don't like drawing ascii-art, sorry).

With this definition the addition of two 'interval<complex>' works
correctly. But unfortunately, the multiplication does not work at all: the
inclusion property isn't respected. Whose fault is it? It's the fault of
the interval arithmetic which only works with continuous numeric types.
And the purpose of the library is to implement these genric operations.

On the other hand, 'complex<interval>' correctly works if 'complex' has
defined generic operations (like '(a,b)*(c,d) = (a*c-b*d,a*d+b*c)'). And
the inclusion property is always respected. It's the reason why a lot of
people have spoken about 'complex<interval>' rather than
'interval<complex>' during this review.

However, the best way to define an 'interval_complex' which isn't
'complex<interval>' is to use a spherical representation: a point 'z' is
in the interval '(a,r)' (of type complex*real) iff '|z-a| <= r'. This way,
by redefining all the operations, you get a new type that respects the
inclusion property. Moreover, in some situations, this type can be more
precise than 'complex<interval>' (since complex multiplication preserves
sphere and not rectangle).

But the operations are no more the generic ones of interval
arithmetic. The new type is no more an interval (there is no bounds, it
can't be linearly traversed, it can't be bisected, etc).

I hope I made it clear there are two straight-forward ways to define a
type on complex that respects the inclusion property. The first one is to
use 'complex<interval>' but it is impeded by the way the Standard defines
'std::complex' (I personally would be happy to have a generic
'boost::complex'). The second one is to use a spherical representation but
it's outside the scope of this library since it doesn't use generic
operations anymore (it doesn't even require the numeric type to be
partially ordered).

Regards,

Guillaume