programmatically optimizing expressions (by removing redundant computations)

Question

I had a pretty big equation that I needed to use to solve for a given variable. So I used an online tool that was capable of rewriting an equation in terms of a given variable. It gave me some huge 700 character equation. I tested it, and it does work.

I can see some pretty obvious redundancies in the equation where it's recomputing a value that could be saved as a temporary variable instead. I could go through the entire equation and optimize it myself, but I'm likely to have to do this with many more equations, so I'd like to automate the process instead.

What are some good tools that will help optimize mathematical redundancies?
(It's just for a personal project, so I'd really prefer something free)

To all those people who I know will ask about this really being necessary: This is performance critical code, and from my experience, the AS3 compiler will not do these kind of optimizations on it's own. Removing redundancies will also make the code more readable.

Answer 1

Look into memoization.

http://en.m.wikipedia.org/wiki/Memoization

Answer 2

As belisarius suggested, putting the equation into a mathematical programming language like matlab, mathematica or maple would allow you to use their simplify and reduction tools to help you.

Here is a list of free matlab like programs http://www.dspguru.com/dsp/links/matlab-clones if you dont want to fork out the high price for a matlab licence.

Answer 3

I've used wxMaxima. It's fairly easy to make it do substitutions, and it's free. I had to crank a lot of massive Laplace transforms, with partial fraction expansions. Once I learned how to use it, it was pretty quick.

Answer 4

Maxima has a useful function called optimize:

Function: optimize (expr)

Returns an expression that produces the same value and side effects as expr but does so more efficiently by avoiding the recomputation of common subexpressions. optimize also has the side effect of "collapsing" its argument so that all common subexpressions are shared. Do example (optimize) for examples.

It would simplify the expression you uploaded to Ideone to:

block(
[%1,%2,%3,%4,%5,%6,%7,%8,%9,%10,%11,%12,%13,%14],
  %1:a^2,
  %2:b^2,
  %3:c^2,
  %4:d^2,
  %5:-%4+2*b*d-%2,
  %6:-%3+2*a*c-%1,
  %7:2*a-2*c,
  %8:2*c-2*a,
  %9:
  %8*d+b*%7,
  %10:%7*d+b*%8,
  %11:i^2,
  %12:j^2,
  %13:-2*%12-4*i*j-2*%11,
  %14:%12+2*i*j+%11,(-sqrt(%4*%14+%3*%14+%2*%14+%1*%14+b*d*%13+a*c*%13+%6*h^2+    (%9*g+2*%3-4*a*c+2*%1)*f+%10*e)*h+%5*g^2+f*(%10*g+%9*e)+(2*%4-4*b*d+2*%2)*e*g+%6*f^2+%5*e^2)-(d-b)*h-(c-a)*g-(b-d)*f-(a-)*e)/(%4-2*b*d+%3-2*a*c+%2+%1))

Not neccessarily more readable, but it contains no more common subexpressions.