[Boost-announce] [boost] [Polynomial] Review Result

Subject: [Boost-announce] [boost] [Polynomial] Review Result
From: John Maddock (john_at_[hidden])
Date: 2009-04-09 12:19:17

Apologies for the delay in putting this together...

First off I'd like to thank the author for submitting this for review  
- I wish all our SOC students were similarly diligent! :-)

We received a number of reviews of this library, but none were in  
favor of acceptance in its current form, and most thought that there  
was still a fair bit of work to do to get the library into shape.   
However, most thought that the library could be accepted into Boost  
given sufficient changes/enhancements.

Therefore the library is not accepted into Boost at this time, but I  
would like to encourage the author to continue to work on the library  
and resubmit at a future time.

In no particular order the main review comments are summarized below:

Principal comments:

* Documentation, especially the background is inadequate and needs a  
good proofreading
a) From the examples are nothing that a competent programmer couldn't  
figure out from the declarations.  Some more interesting or useful  
examples would be nice, particularly for things like the special forms.
It's not exactly clear what I would do with those functions.
b) There is no documentation or references to the various algorithms  
used. Those, too, would be nice.
c) Doc.html appear to have been created 'the Hard Way'.  Would be much  
more useful and look nicer if produced with the Quickbook, Doxygen...  
toolchain.  And make it maintainable by other people.

* Use of constructors and assignment operators that modify their  
arguments isn't acceptable - best to find another interface for this.

* Several reviewers noted that the code didn't build for them, in  
particular log2 isn't available on all platforms/compilers.

* evaluate_polynomial() and evaluate_polynomial_faithfully() take  
their coefficient arguments in the opposite order of all the other  
functions/constructors in the library, without providing any reason  
for that choice.  That's seems somewhat surprising.  I'd suggest  
fixing that, or at the very least providing an argument in the  
documentation why this makes some sense.
* Rename evaluate() to horner() and provide evaluate() as an inline  
call to horner().

* Rename evaluate_faithfully() to compensated_horner().

* Things that say "Be careful about this" generally need fixing.

* It would be nice to have operator* and operator/ as well as *= and /=.

* Considering they share the same core algorithm, it might be nice to  
have a function that could do division and return the remainder at the  
same time. Something like
poly::divide(P &divisor, P &quotient, P &remainer)

* FFTs are good for multiplying polynomials above a certain size, but  
they are rather heavy for small polynomials and can lead to unexpected  
crosstalk between terms.  There should be an option for * that doesn't  
use the FFT, and it should be the default for small polynomials.

* operator/= has a hardcoded "std::vector<double> new_coefficients"  
that later gets rounded??  This should be fixed to work with any type  
that fulfills the necessary
conceptual requirements (and tested and documented what those  
requirements are - it would be nice  if they were the same as the rest  
of Boost.Math).

* The name FieldType is mathematically misleading since the  
instantiating type is very likely not to be a field (e.g. int or a  
multiple precision integer type).

* the Polynomial class provides a fairly minimalist set of supported  
functions. This may well be deliberate (if so, apologies), but I would  
like to see a richer interface including such things as
           - content (gcd of coefficients, where that makes sense)
           - polynomial discriminant
           - resultant of 2 polynomials
           - evaluation of homogeneous polynomial ( f(x) = sum c_i  
x^i,f(a,b) = sum c_i a^i b^(d-i) )
           - evaluation at a polynomial (f(g(x)))
           - Pseudo-division of polynomials
           - finding roots over C
           - finding roots over F_p
           - factorisation over Z
           - factorisation over F_p

* We had one feature request for extending support to finite fields.

* 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?

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

* 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?

Regards,
John Maddock
Review Manager for Polynomial Library.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost