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

From: Guillaume Melquiond (gmelquio_at_[hidden])
Date: 2002-09-08 07:42:52

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).

> > 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.

> > 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.

> 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"... :-)

> - 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));

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,

Guillaume