[GiNaC-devel] [PATCH] {add, power}::eval(): convert terms into primitive polynomials when possible.

[Richard B. Kreckel]

Hi!

Sheplyakov Alexei wrote:
> On Sat, Aug 11, 2007 at 11:11:57PM +0200, Richard B. Kreckel wrote:
>> One of the points of choosing the algorithms that are done at the eval()
>> stage to be only subquadratic algorithms was that otherwise one might be
>> unable to merely construct the ex object.
> 
> I think this requirement is way too strict. I'd say anything of polynomial
> complexity (with "reasonable" coefficients) is OK.


Not for add objects! And we really had evaluation of sums in mind when 
we said "no quadratic algorithms", well knowing that matrix::eval may be 
much worse without anybody realistically running into trouble (but that 
depends on how you count, in a sense).

Your data shows that mul::eval() has never been subquadratic and nobody 
has noticed so far. This suggests that different criteria and benchmarks 
apply for varying kinds of objects.


>>> My patch causes overhead even in the trivial case, e.g. when the
>>> polynomial is already unit normal. Consider e.g. 
>>>
>>> e = (x+1)*(2*x^2+x+1)*...*(100*x^100+99*x^99+...+1);
[...]
> This gives a beautiful parabola (both with my patch or without it).
> Coefficients are different, but both versions of mul::eval() are
> quadratic.


This is interesting. Taking logarithms of both axis it appears like the 
behavior is indeed O(n^2.5) in both cases.

I don't know what others think. For my own part, you've dissolved my 
worries.

Jens wants to roll a release. I guess he would be interested whether 
your last patch cuts it: is it worth applying or not?

Cheers
   -richy.
-- 
Richard B. Kreckel
<http://www.ginac.de/~kreckel/>