Re: [boost] [Review] Polynomial library review begins today

Subject: Re: [boost] [Review] Polynomial library review begins today
From: Pawe³ Kieliszczyk (lord.zerom1nd_at_[hidden])
Date: 2009-03-11 06:47:28

Hi everyone,

I'll try to to answer for a few question that have already appeared and
explain some implementation issues.

Neal Becker wrote:

> 1) The first text is 'Background'.  We need some introduction here.  An

> overview of the purpose of the library.

I guess you're thinking of docs. I'll try to add the introduction soon.

> 2) """

> Modification from std::vector:

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

>

>  This function uses the nested std::vector::swap() function. The c vector

> should contain new coefficients.

> """

>

> Does this mean that the vector 'c' is modified?  I can't accept this.
 This

> really violates the principle of least surprise.  Noone expects an
operator=

> to act like that.

The reason I decided to add this was performance. Using std::vector::swap()
function works faster than copying all coefficients.

It might be useful while creating polynomials. We could prepare the
coefficients in std::vector() and then simply swap it.

On the other hand I agree that using it in operator= is not a good choice.

Do you thing that such a function that uses std::vector::swap() should exist
in the lib? Actually it doesn't have to be supported but might be.

Ross Levine wrote:

> After review, I can't find any support for polynomials over finite

> fields. I would argue that no polynomials library is complete without

> this functionality built-in. At the very least, one should be able to

> specify an irreducible polynomial in a finite field and use that as

> the basis for another field. Better would be a way to know if some

> polynomial is irreducible over its field. This library doesn't help me

> much without that functionality.

>

> I think the library needs this functionality very badly.

True. There is no support for this. However, I am not sure I could add this
functionality during the review. I think I would need more time and
reflections.

> Documentation needs proofreading and some fixing, there's some

> grammatical issues.

Yea, I realize that my english isn't good but I try my best.

Ravi wrote:

> On Tuesday 10 March 2009 08:23:07 John Maddock wrote:

> > Download of the zip file from the vault is here:

>

> Is this the latest version? It does not compile for me, since
polynomial.hpp

> uses pow on lines 370 and 372. It needs to include cmath and also needs a

> "using std::pow;" statement.

>

> Second, there are compile errors upon trying to multiply two polynomials

> together (code attached). I am using boost 1.38.0 with gcc 4.3.2 on Linux

> x86_64.

Hm... I've been writing the library on Linux platform using Boost 1.36.0. As
far as I know my mentor Fernando Cacciola was using the lib on Windows and
he hasn't notified me about any problems.

Kevin Lynch wrote:

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

Yea. We've been thinking about this problem with Fernando. I'll paste here
the justification I send to him once:

> Evaluation may be implemented in 4 ways:

> i) same as now: *first is the coefficient for x^n term and *(last-1) is
the

> coefficient for x^0 term. Implementation is very simple and fast, then.
> ii) using bidirectional iterator. Thus, *first would be the coefficient
for x^0

> term, but operator-- should be provided.
> iii) using sperator[] like in the rational.hpp from boost libraries

> template <class T, class U>
> inline U evaluate_polynomial(const T* poly, U const& z, std::size_t count)
> {
>    BOOST_ASSERT(count > 0);
>    U sum = static_cast<U>(poly[count - 1]);
>    for(int i = static_cast<int>(count) - 2; i >= 0; --i)
>    {
>       sum *= z;
>       sum += static_cast<U>(poly[i]);
>    }
>    return sum;
> }

>

> iv) We could also copy and reverse all coefficients if *first is the
coefficient

> for x^0 term, then evaluate.

>

> I don't know which way would be the best. Do you have any other ideas?

After a short discussion we decided to implement it the way you can see.

-- 
Pawel Kieliszczyk