[GiNaC-devel] Re: Asymptotic behaviour of mul::eval() and add::eval()

[Richard B. Kreckel]

Hi Alexei!

Sheplyakov Alexei wrote:
> On Mon, Aug 13, 2007 at 10:44:59PM +0200, Richard B. Kreckel wrote:
>> And I suppose it is clear by now that this is due to the fact that the 
>> problem is really quadratic in input size -- as was the original problem
>> where the top-level object was a mul instead of an add.
> 
> The sum has 3N terms, and the product has N terms. Why the problems
> are quadratic?


Because of the children terms:

{ echo "plot '-' using 1:2 with lines title 'characters in term to be 
evaluated'"
echo
for N in `seq 100 100 2000`; do
SIZE=$({ echo -n "(0001+0.0001*x)"
          for i in $(seq 2 $N); do
	         echo -n "*(0001+0001*x"
		     for j in $(seq 2 $i); do
			     printf "+%04d*x^%04d" ${j} ${i}
			     done
		     echo -n ")"
		      done
	  echo ";" ; } | wc -c)
echo "$N $SIZE"
done
echo "e" ; } | gnuplot -persist '-'

:)

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