[GiNaC-devel] Re: Asymptotic behaviour of mul::eval()
and add::eval() [Was: PATCH...]
Richard B. Kreckel
kreckel at ginac.de
Mon Aug 13 22:44:59 CEST 2007
Hi,
Sheplyakov Alexei wrote:
> 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 '-'
Experimentally, this is O(N^2.2) on my machine.
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.
So, I dare say that O(N^2.x) is actually pretty good for a problem that
has input size O(N^2), right?
Best wishes
-richy.
--
Richard B. Kreckel
<http://www.ginac.de/~kreckel/>
More information about the GiNaC-devel
mailing list