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

[Sheplyakov Alexei]

Hello!

On Sun, Aug 12, 2007 at 11:30:57PM +0200, Richard B. Kreckel wrote:

> Not for add objects! And we really had evaluation of sums in mind when 
> we said "no quadratic algorithms",

Unfortunately, add::eval() is not subquadratic either. For example,

1 + \sum_{i=1}^N (i x_i + (i+1) x_i^i x_{i+1}^{i+1} + (i+2) x_i^i x_{i+2}^{i+2})


#!/bin/sh
{ echo "plot '-' using 1:2 with lines title 'add::eval() asymptotic behaviour'"
  echo
for N in `seq 100 100 3000`; do
TIME=$({ echo -n "time(1"
         for i in $(seq 1 $N); do
					 j=$(expr $i + 1)
					 k=$(expr $i + 2)
					 printf "+${i}*x${i}+${j}*x${i}^${i}*x${j}^${j}+${k}*x${i}^${i}*x${k}^${k}"
				 done
				 echo ");" ; } | ginsh | sed -e 's/s//g')
echo "$N $TIME"
done
echo "e" ; } | gnuplot -persist '-'

Best regards,
 Alexei

-- 
All science is either physics or stamp collecting.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 827 bytes
Desc: Digital signature
Url : http://www.cebix.net/pipermail/ginac-devel/attachments/20070813/04ab19bb/attachment.pgp