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

From: Joerg Walter (jhr.walter_at_[hidden])
Date: 2002-09-08 14:23:06

----- Original Message -----
From: "Guillaume Melquiond" <gmelquio_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Sunday, September 08, 2002 2:42 PM
Subject: Re: [boost] Formal Review for Interval
Library(was:IntervalLibraryreminder)

> On Sun, 8 Sep 2002, Joerg Walter wrote:
>
> > > So, here is the problem: we need to convert 'interval<T1, P1>' to
> > > 'interval<T2, P2>'.
> >
> > The first case I'm interested in is interval<T1, interval_traits<T1> >
and
> > interval<T2, interval_traits<T2> > (because that's what I tested ;-).
> >
> > > If all elements of T1 are exactly representable by
> > > elements of T2, there is no problem: a cast is enough.
> >
> > Correct, so we should be able to get
> >
> >     interval<double> ris1 = 0;
> >     interval<float> ris2 = 0;
> >     // Doesn't work.
> >     // std::cout << ris1 + ris2 << std::endl;
> >     std::cout << ris1 + interval<double> (ris2) << std::endl;
> >
> > without risk, at least? This would be very helpful, because we then
could
> > use
> >
> >     vector<interval<double> > riv1 (1);
> >     vector<interval<float> > riv2 (1);
> >     riv1.clear ();
> >     riv2.clear ();
> >     // Doesn't work.
> >     // std::cout << riv1 + riv2 << std::endl;
> >     std::cout << riv1 + vector<interval<double> > (riv2) << std::endl;
> >
> > immediately, i.e. std::complex and boost::interval would behave similar
> > w.r.t. basic linear algebra.
>
> Yes, converting from float to double is an exact operation (I'm speaking
> about IEEE-754 types here).

Ok, so this would be a workable solution, although not optimal due to the
temporary vector.

> > > But what if an
> > > element of T1 can't be represented? We need to convert it
> >
> > This isn't a new problem, the same can happen, when converting a double
to a
> > float.
> >
> > > and respect the
> > > inclusion property of interval arithmetic.
> >
> > Maybe this is a new problem. What do other interval libraries do here?
>
> Profil/BIAS, MPFI, CGAL use only one base type so they don't have any
> problem with conversions. Sun Interval Library provides interval
> conversion constructors, but the library only deals with primitive
> floating-point types and only works on x86 and Sparc.

Ok, I accept that this is a somewhat unusual problem and may or may not be
solvable in the framework you constitued.

> > > Somebody could probably object that with 'promote_traits', we always
are
> > > in the first case if 'promote_traits' is correctly built. But, in my
> > > opinion, if an interval can never get back to a less precise type, all
the
> > > mixed operations stuff is useless.
> >
> > Generally agreed. But if you build your promote_traits correctly, the
user
> > of the interval library only needs to consider the cases where going
back to
> > a less precise type, at least.
>
> Yes I completely agree with you; but it's exactly these cases which are
> problematic.

Are you saying here, that the user isn't able to get some sensible
information to decide manually how to proceed when going back to a less
precise type?

> > Ok. First of all, I'm neither too familiar with your current
implementation
> > nor with the pitfalls of policy based design in general. As far as I
see,
> > the following transformation of ublas experiences restricted to the
> > simplified case might help:
>
> You didn't have to go that far. I already had agreed that defining mixed
> operations was no problem once there are interval conversions. And even if
> you are not familiar with all of that, your code is quite good. :-)
>
> > - adding a templated constructor
> >
> >   template<class T, class Traits = interval_traits<T> >
> >   class interval {
> >     // Need some magic to allow only types U, which are representable by
T
> >     template<class U>
> >     interval (interval<U, interval_traits<U> >);
> >   }
>
> Yes, the "magic"... :-)

template<class U, class T>
struct representable_traits {
   typedef char result [];
};

template<>
struct representable_traits<float, double> {
   typedef char result [1];
};

template<class T>
class interval_traits {
};

template<class T, class X = interval_traits<T> >
class interval {
public:
    interval () {}

    template<class U>
    interval (const interval<U, interval_traits<U> > &, typename
representable_traits<U, T>::result = 0) {}
};

int main () {
    interval<float> fi;
    interval<double> di;

    interval<double> iv1 (fi);
    interval<double> iv2 (di);
    interval<float> iv3 (fi);
    // Doesn't compile.
    // interval<float> iv4 (di);
    return 0;
}

I'm sure the metaprogramming gurus could come up with a better solution ;-)

> > - writing some type promotion traits
> >
> >   template<>
> >   struct promote_traits<interval<double>, interval<float> > {
> >     typedef  interval<double> result_type;
> >   }
> >
> > - implementing some binary operators
> >
> > template<class T1, class T2> inline
> > typename promote_traits<interval<T1>, interval<T2> >::result_type
operator+(
> >          const interval<T1>& x,
> >          const interval<T2>& y)
> > {
> >   typedef typename promote_traits<interval<T1>, interval<T2>
>::result_type;
> >   if (interval_lib::detail::test_input(x, y))
> >     return result_type::result_type::empty();
> >   typename result_type::rounding rnd;
> >   return result_type(rnd.add_down(x.lower(), y.lower()),
> >        rnd.add_up  (x.upper(), y.upper()), true);
> > }
>
> I would have written it differently; the computation functions need to
> receive arguments of the same type, so it would have been:
>
>   typedef typename result_type::base_type T3;
>   T3 xl = rnd.convert_down<T1>(x.lower());
>   T3 xu = rnd.convert_up  <T1>(x.upper());
>   T3 yl = rnd.convert_down<T2>(y.lower());
>   T3 yu = rnd.convert_up  <T2>(y.upper());
>   return result_type(rnd.add_down(xl, yl), rnd.add_up(xu, yu));

I understand that something like this is necessary to get a generic solution
including policies, but is this really neccessary for the simplified case of
float to double promotion?

> And the problem lies in the definition of 'convert_'. On one hand, that's
> something that is closely related to 'rnd'; and on the other hand, the
> user should be able to easily add some new conversions. And we weren't
> able to find a solution for this problem.
>
> So rather than letting the user "play" with some heavy mecanisms, we
> thought that it was better not to support interval conversions and let the
> user define the conversions outside the library.

Regards

Joerg