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

Edit> Expression reduced form 700 to 20 chars below

Try to use FullSimplify in Wolfram Alpha, or Mathematica.

WolframAlpha FullSimplify(x^2+2 x +1)

Edit ->

Thinking again, Mathematica does not need to simplify your one var equation to solve it ... the Solve command (or FindRoot, or FindInstance ...) will do it.

Try for example

WolframAlpha Solve(x^2+2*x+1=0 , x)

EDIT -> Just to make the answer free of dependencies from ideone.com, your 700 char equation after some simplifications becomes

   t= -((E*A+B*F+ Sqrt(2*A*E*F*B+ A^2*(I^2-F^2) + B^2*(I^2-E^2))) /(A^2 + B^2))

Where

   E = e - g
   A = a - c
   B = b - d
   F = f - h
   I = i + j

Please check if the Sqrt argument is a perfect square, based on other "geometrical" considerations ... it barks and has a tail ... is it a dog?

EDIT -> Guesswork:

I don't have any proof, but the symmetry of the equation suggests that in your problem

  E^2 = (I^2-F^2)  => (e-g)^2 = (i+j)^2 - (f-h)^2

If so is the case (please verify it), your equation becomes

  t= -((E*A+B*F+ Abs(E*A+B*F)) /(A^2 + B^2))

If AE+BF > 0 (and I guess it is so, because if not t===0)

  +-----------------------------------+
  ¦  Your 700 chars equation comes to ¦
  ¦                                   ¦
  ¦ t= -2 * (A*E + B*F) / (A^2 + B^2) ¦
  ¦                                   ¦
  +-----------------------------------+

short and sweet ... :)

Answer 2

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 3

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.

Answer 4

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.