Boost logo

Boost :

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


Boost list run by bdawes at, gregod at, cpdaniel at, john at