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

Richard B. Kreckel kreckel at ginac.de
Sun Aug 12 23:30:57 CEST 2007


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 

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

Richard B. Kreckel

More information about the GiNaC-devel mailing list