Re: [boost] [Boost-users] [Review] Polynomial library review begins today

Subject: Re: [boost] [Boost-users] [Review] Polynomial library review begins today
From: John Maddock (john_at_[hidden])
Date: 2009-03-17 14:29:58

A little later than planned, here is my review of the polynomial library:

Documentation and Design
~~~~~~~~~~~~~~~~~~~~~~~~

As previously noted by others the Introduction doesn't adequately describe 
the library - some sort of simple tutorial at this point would be useful 
too.  The "Background" section doesn't really describe the "background" as 
such either.

This constructor:

template<typename U>
polynomial(const U& v);

had me a little confused at first - is there any advantage to making this a 
template rather than simply accepting a const FieldType& as the single 
argument?

This constructor:

polynomial(std::vector<FieldType>& c);

should *not* modify the original vector IMO, a construct-with-move should be 
a separate constructor - I'm sure we have a move/rvalue reference emulation 
library available somewhere?  Likewise for the assignment operator 
polynomial<FieldType>& operator=(std::vector<FieldType>& c);

It's not clear from the documentation what this constructor does:

polynomial(InputIterator first1, InputIterator last1, InputIterator first2);

It needs to clearly state the degree of the resulting polynomial and whether 
it passes through all/any of the points - in fact maybe the constructor 
should have a final parameter for the degree of the polynomial and use 
least-squares fitting when required?  Likewise for the member function 
template<typename InputIterator> void interpolate(InputIterator first1, 
InputIterator last1, InputIterator first2);

Operators:  the / and % operators need good descriptions of what they do, 
given that no exact division is possible.  As someone else has already 
noted, a function to calculate divide and remainder in one step would be 
useful too.

GCD: presumably this is restricted to polynomials with integer coefficients? 
If so it should say so.

Evaluation: The docs should say what method is used for the 
evaluate_faithfully method and give a reference.  Renaming as someone else 
suggested may be better too, but personally I'm easy either way on that. 
I'm not sure whether there should be an evaluate_by_preconditioning method, 
shouldn't the polynomial "know" that it has been preconditioned and react 
accordingly.  I haven't looked/checked but do the usual arithmetic operators 
still work if the polynomial has been preconditioned?  I assume probably 
not, but if that's the case there should be a stern warning to that effect, 
*and* checks in code to prevent us from doing something stupid :-)  BTW, 
preconditioning can be applied to polynomials of any degree I believe it's 
just that it gets hard to implement in the generic case.

In addition I'd like to see the evaluation functions templated, so that the 
type being evaluated can differ from FieldType - it would surely be quite 
common for example to create and manipulate polynomials with integer 
coefficients, but then want to evaluate on a floating point type.  There is 
machinery in Boost.Math BTW to handle the mixed argument-promotion and 
calculation of the result type, let me know if you need help in using this.

Special Forms: the functions provided do *not* generate polynomials in the 
alternative forms, but rather generate the named polynomial of order N, 
which is rather less useful, but at the very least the docs need updating to 
reflect this.

Implementation
~~~~~~~~~~~~~~

I haven't spent a great deal of time on this, but I note that:

test_arithmetics.cpp fails on cygwin: or at least it did once I added a

    using std::pow;

to start of operator*= to get things compiling.

None of the code builds with msvc: there are a couple of issues here:

    friend polynomial<FieldType> 
boost::math::tools::gcd<>(polynomial<FieldType> u, polynomial<FieldType> v);

Needs to be changed to:

    friend polynomial<FieldType> 
boost::math::tools::gcd<FieldType>(polynomial<FieldType> u, 
polynomial<FieldType> v);

to get msvc to Grok the code.

After that there are a bunch of failures due to the use of log2 which msvc 
doesn't support (and since it's not part of the std other compilers are 
likely to complain too).

I haven't looked too hard at the implementation, except to echo the comments 
posted previously that the Conceptual requirements for FieldType need 
documenting and *testing*.  There are concept checking classes and 
archetypes in Boost.Math which may be of use here.  Again, shout if you need 
help in figuring out how to use these.  I did notice that operator*= for 
example uses std::complex<double> internally which effectively limits the 
precision that can be achieved - to be useful to me - and to replace the 
existing "implementation detail" polynomial class in Boost.Math - I would 
need the polynomial class to be usable with arbitrary precision types such 
as NTL::RR or mpfr_class.  Also as previously noted, multiplication of small 
polynomials may well be more efficient with the "naive" algorithm, so some 
performance tests and experimenting is required here.  Related to this, use 
of "round" should be restricted to types that are known to be integers?

* What is your evaluation of the potential usefulness of the library?

As noted by others it's a niche library but potentially quite useful within 
that niche.

* Do you think the library should be accepted as a Boost library? Be
sure to say this explicitly so that your other comments don't obscure your
overall opinion.

I think that the library could be accepted into Boost, but not it's it's 
current form, so I would vote no for now: please note this is my personal 
review of the library and should not be confused with my role as review 
manager for this library.

Regards, John Maddock.