MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

Locating common subexpressions

  • To: mathgroup at smc.vnet.net
  • Subject: [mg69429] Locating common subexpressions
  • From: carlos at colorado.edu
  • Date: Tue, 12 Sep 2006 06:52:51 -0400 (EDT)

The strangest thing about the behvior of Simplify in my
previous post can be seen at a glance:

  R = (3 + 3*a^2 + Sqrt[5 + 6*a + 5*a^2] + a*(4 + Sqrt[5 + 6*a +
5*a^2]))/6
  R = Simplify[R,a>=0]
  (3 + 3*a^2 + Sqrt[5 + 6*a + 5*a^2] + a*(4 + Sqrt[5 + 6*a + 5*a^2]))/6

The subexpression Sqrt[5 + 6*a + 5*a^2] is not located. Ideally
Simplify should right away replace that by a temp, say t$, and
get to work on

  (3 + 3*a^2 + t$ + a*(4 + t$))/6

where from the assumptions, t$>0 and real. Of course the leaf count
of t$ should influence subsequent transformations.
This initial pass is useful in complicated expressions that come, eg,
from an equation solver since messy subexpressions like the
discriminant may appear in several places. I had some of those
with leaf counts in the tens of thousands.

Locating common subs is of course an key task of optimizing
compilers. Simplification and compilation share some objectives,
although compilers have to deal with timing and side effects. In fact
I wouldnt mind at all if Simplify would return a compound expression:

Block [{t$}, t$=Sqrt[5 + 6*a + 5*a^2];  (3 + 4*a + 3*a^2 + (1 +
a)*t$)/6 ]

since this is perfect for documentation, or conversion to low-level
code.


  • Prev by Date: memory leak problem
  • Next by Date: Re: StylePrint and 2D strings
  • Previous by thread: memory leak problem
  • Next by thread: Re: Locating common subexpressions