
Boost : 
Subject: Re: [boost] Math tools polynomial enhancements
From: Jeremy Murphy (jeremy.william.murphy_at_[hidden])
Date: 20151029 09:34:10
Hi John,
On 29 October 2015 at 21:22, John Maddock <jz.maddock_at_[hidden]> wrote:
>
>
> On 27/10/2015 21:49, Jeremy Murphy wrote:
>
>> I was just looking at the polynomial class and thinking that it could be
>> enhanced substantially with more operators. Presumably with division and
>> remainder it would be a Euclidean ring and then you could even call gcd on
>> it.
>>
>
> This is something of an open question.
>
> I think there is a place for polynomial manipulation within Boost, but I'm
> not sure that this class is the best basis. As we say in the docs, it's a
> braindead implementation that's good enough for what I needed at the time
> to implement Boost.Math, but not really suitable for heavy duty polynomial
> manipulation.
Well, I think "braindead" is a little harsh, it seems quite reasonable to
me for a generalpurpose univariate polynomial class. I must admit though,
I don't particularly like the choice of constructors and the degree member
function will return the maximum value of size_t when size == 0.
What do you think of the idea then of making this polynomial class a
proofofconcept in terms of functionality? In the future the class could
be given a heavy duty redesign, without, I hope, having to reimplement too
much. But even if the redesign was never done, we would still have this
class, with added functionality.
Division is interesting because it's not actually clear to me what the
> result should be  is it a polynomial (plus remainder) or is it a rational
> function (suitable reduced by the greatest common divisor).
>
Yes, I was initially troubled by this question but resolved, admittedly
more through intuition than proof, that polynomial division is Euclidean
(integer) division: the / operator gives you the quotient, and % gives you
the remainder. Someone with a deeper understanding of abstract algebra
could presumably validate or discredit this claim. However, if one accepts
this, then everything falls neatly into place, for example the /= operator
makes sense, which it obviously wouldn't otherwise.
I think it probably needs to be written by someone who has a concrete use
> case and is deeply familiar with the theory, I don't know if that's you,
> but I do know it's not me ;)
>
I admit that I am mostly drawn to this problem by fascination and wonder
rather than a pragmatic need to get something done. But I think you're
right, it's important to have a concrete use case rather than just throwing
operators at a class to see what sticks. So GCD is the use case I propose,
starting with the Euclidean algorithm and then the Stein algorithm. I'm not
an expert in this area but I have a pretty good idea of what needs to be
done.
Cheers.
Jeremy
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk