On Sep 11, 2009, at 6:56 PM, Richard Fateman wrote:
> Sure, you can write a program which tries one thing and another in
> some brute-force way.
>
> There's nothing to prevent people from writing such a program in
> Maxima except for
> the two items you already mentioned.
>
> 1. You will probably end up with a brute force method which could
> take a long time to run on exactly the kinds of expressions for
> which it matters: large ones.
> I am assuming that you need to partition subexpressions e.g. a+b+c+d
> +e...+z --> simplify(a+c+d+..) + simplify(b+e+ ...) + ... Or do
> other combinatorial rearrangements. If you just call ratsimp()
> or factor() or radcan(), then that's not cheap either, but it is
> not as effective.
> (e.g. factorsum).
> 2. You need to have some way of terminating the search, or deciding
> which possible result is best.
>
> You could give hints, like functions to include in the answer,
> functions to exclude from the answer, how to evaluate complexity,
> assumptions to use.
> Mathematica and Maple do things like this. Check their documentation.
>
> Your draft of a simplify program looks like a good start.
>
> RJF
>
Thanks for the hint of checking documentation - I've implemented
mathematica's LeafCount[] which is one of the main quantifiers for
their Simplify[]. It's much simpler than my 'cost' function, but
works great. It's very fast too. For simple expressions my
$leaf_count gives the same number as Mathematica - 'fullform' is
pretty similar to how Maxima handles expressions...
In[24]:= FullForm[y/x]
Out[24]//FullForm= Times[Power[x,-1],y]
It's true - brute force is merely brute force, but today's computers
can do plenty in a second or two and the user is generally prepared
to wait for a second to get a simplified answer (because he/she knows
how long would it take him to do it on paper). 'simplify' is
expensive.. even in Mathematica you can wait for very long with some
expressions (from documentation):
This takes a long time, due to trigonometric expansion, but does not
yield a simplification:
In[1]:= Simplify[2Sin[10x+11y+12z]Cos[10x+10y+10t]]//Timing
Out[1]= {40.709,2 Cos[10 (t+x+y)] Sin[10 x+11 y+12 z]}
So I wouldn't worry too much about efficiency if the function is
simply too convenient not to have. Of course 'thou shall not cons in
vain' always applies and if something can be considerably sped up, it
should be...
Searching on the internet for such 'simplify' algorithms didn't get
me much - I hoped there would be resources regarding this. Perhaps
there's not much to it - just a simple brute force search with
perhaps some tricks.
Already in this infantile stage I find my implementation 'simplify'
useful - probably mainly because I never managed to remember various
Maxima's simplifying functions (I've first heard of 'factorsum'
today)... and this is probably the case for many Maxima users
(developers and expert users excluded).
I'll do some more work on it - to see what can be done with such
approach...
(defun $cost (expr)
(if (atom expr)
1
(1+ (apply #'+ (mapcar #'$cost (rest expr))))))
This is the maxima's 'leaf_count', works great as quantifier for
expression complexity.
Regards,
Ziga