Subject: [ maxima-Bugs-609464 ] 1+%e,numer and %e^%e,numer
From: Richard Fateman
Date: Wed, 20 May 2009 21:49:28 -0700
Dieter Kaiser wrote:...
... snip...
>
> On my slowest system with CLISP the testsuite has a run time of about
> 1050 seconds and calls simplifya about 2*10^7 times. The contribution of
> the extra tests for $numer and $%enumer I have estimated to be less than
> 1 second. (I have written some special test functions to measure the
> effect.)
>
I am not surprised. The majority of the time of simplifya is probably
spent doing sorting (comparing using alike and great) inefficiently.
Essentially every sum and product simplification involves an insertion
sort into a list, taking O(n^2) and maybe O(n^3) time.
Various programs that change the mechanism to be O(n log n) or O(n)
using a hash table make the simplifier much faster overall.
/ /I think the rationale to remove the $numer check is more of an
aesthetic issue -- if it can be done easily, the program looks better.
> So, I think the effect of the extra test is negligible.
>
If simplifya were made, say, 40 times faster by using a hash table, then
the cost of the test for $numer would be, proportionally, much higher.
RJF