On Sat, Aug 11, 2007 at 11:11:57PM +0200, Richard B. Kreckel wrote:
It is not some overhead that worries me. Rather, it is the algorithmic complexity of the new overhead. The new transformation appears to introduce quadratic behavior at the eval() level.
[snipped]
Looking at the code it appears to me like mul::eval recurses now.
mul::eval calls evalchildren, so it is recursive even without my patch.
Well, but that recurses into *children* only! At the end of the loop that you introduced into mul::eval(), a new mul object is returned. It is not evaluated yet and enters mul::eval() again. And it might contain most of the original terms. This is an entirely different quantity of recursion that is responsible for potentially quadratic behavior, IINM.
mul::eval() *is quadratic* even without my patch: ex mul::eval(int level) const { std::auto_ptr<epvector> evaled_seqp = evalchildren(level); if (evaled_seqp.get()) { // do more evaluation later return (new mul(evaled_seqp, overall_coeff))-> setflag(status_flags::dynallocated); } If evaluation of children gives something non-trivial, a new mul object is returned. It is not evaluated and enters mul::eval() again.
That's bad.
My patch increases the coefficient. And that is indeed awful.
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.
Wouldn't it be faster to collect the coefficients in one sweep?
I've tried this (see the patch [1]), it has almost no effect.
It still appears to be quadratic. Must it really be quadratic?
Yes. After numeric coefficients are collected, some re-evaluation is necessary. For example, (3*x+3*y)*(x+y) -> (3*(x+y)*(x+y)).eval() -> 3*(x+y)^2 1/9*(9*x+9*y)*(x+y)^2 -> ((x+y)*(x+y)^2).eval() -> (x+y)^3 (N.B.: the result is not mul object)
Well, I recognize that most terms will be trivial in the following recursions, but still.
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);
Indeed. This expression is well suited to study the asymptotic behavior:
$ { echo -n "time((1+x)"; for i in $(seq 2 100); do echo -n "*(1+x"; for j in $(seq 2 $i); do echo -n "+${j}*x^${j}"; done; echo -n ")"; done; echo ");";} | ginsh-1.3.5 0.089994s
To make the test a little bit more interesting, let's take more than 2 points: { echo "plot '-' using 1:2 with lines title 'mul::eval() asymptotic behaviour'" echo for N in `seq 100 100 2000`; do TIME=$({ echo -n "time((1+x)" for i in $(seq 2 $N); do echo -n "*(1+x" for j in $(seq 2 $i); do echo -n "+${j}*x^${j}" done echo -n ")" done echo ");" ; } | ginsh | sed -e 's/s//g') echo "$N $TIME" done echo "e" ; } | gnuplot -persist '-' This gives a beautiful parabola (both with my patch or without it). Coefficients are different, but both versions of mul::eval() are quadratic. Best regards, Alexei -- All science is either physics or stamp collecting.