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/>