Subject: Re: [boost] [Review] Polynomial library review begins today
From: Pawe³ Kieliszczyk (lord.zerom1nd_at_[hidden])
Date: 2009-03-11 06:47:28
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.
> really violates the principle of least surprise. Noone expects an
> 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
> 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.
> 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
> 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
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
> choice. That's seems somewhat surprising. I'd suggest fixing that, or at
> very least providing an argument in the documentation why this makes some
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
> coefficient for x^0 term. Implementation is very simple and fast, then.
> ii) using bidirectional iterator. Thus, *first would be the coefficient
> 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
> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk