Re: [boost] Domain library

From: John Bytheway (jbytheway+boost_at_[hidden])
Date: 2008-07-28 15:34:22

Brook Milligan wrote:
> To make the discussion of the Domain library a bit more concrete, I
> have posted a web page
> 
>      http://abies.nmsu.edu/software/domain/polynomial_library.html
> 
> describing an example of using it to develop (a tiny part of) a
> polynomial library.  For the moment it is a pretty raw page with
> broken links, etc.  However, perhaps it will serve to give a better
> flavor of how this can be used to build other libraries.
> 
> Even better, perhaps it will give a better opportunity for you to
> contribute new ideas that will improve the library.

I'm concerned about the behaviour of standard algorithms in this 
context.  For example, consider a general 'power' function

template<typename T, typename Integer>
power(T, Integer);

which will involve a lot of multiplying.  Adapting your example code, if 
we do this:

typedef polynomials::polynomial<>::type polynomial_c;
typedef polynomials::polynomial_pv<>::type polynomial_pv;

polynomial_c  p1, p2;

p2 = power(p1, 100);

then the power function will be instantiated with T=polynomial_c, which 
(depending on its exact implementation) will probably lead to many 
conversions back and forth between polynomial_c and polynomial_pv.  More 
efficient would be to convert once at the beginning and once back at the 
end.  (Of course even more efficient is probably to have a 
polynomial-specific power function, but one can't be expected to 
reimplement every generic algorithm for polynomials).

To get efficient behaviour here the user will have to realise that power 
will involve a lot of multiplications and pass the appropriate type to 
it.  This is less than ideal.  It's even worse if the algorithm is best 
implemented by first doing lots of computation in one domain and then 
doing a lot in another.

I'm not sure what the best solution is, but one possibility is this:

Support a runtime-domained type, which acts something like a 
variant<polynomial_c, polynomial_pv>, but with operators defined on it. 
  The operators will return a polynomial in whatever representation is 
most convenient for them, which in the case of multiplication will 
always be polynomial_pv.  When you pass this type to power it will 
automatically be working with polynomial_pv variables after one round of 
multiplications, and (again, depending on the specific implementation) 
it may only have to switch domains once.

The user can now pass this type to an algorithm whenever they're not 
sure which domain is most appropriate for it.

The down side of this of course is that there's additional runtime cost 
with every operation.  It's possible (but I don't think likely) that 
most of this could be optimized away in simple cases such as the above 
if all the operators are inlined.

John