# How to decompose a complex expression containing repeated subexpressions? [duplicate]

Suppose I have an expression like

1/8 + 1/8 Sqrt[1 - 28 (2/(3 (Sqrt[4197] - 9)))^(1/3) + 2 (2/3)^(2/3) (Sqrt[4197] - 9)^(1/3)]
- 1/2 Sqrt[1/8 - (1/2 (Sqrt[4197] - 9))^(1/3)/(4 3^(2/3)) + 7/(2 2^(2/3) (3 (Sqrt[4197] - 9))^(1/3))
- 7/(8 Sqrt[1 - 28 (2/(3 (Sqrt[4197] - 9)))^(1/3) + 2 (2/3)^(2/3) (Sqrt[4197] - 9)^(1/3)])]


which contains repeated common subexpressions. I am interested in an algorithm that can decompose it into parts of the minimal (or close to minimal) total complexity. The expected output should be something like this:

(1 + α - Sqrt[3 - β - 14/α]) / 8
/. α -> Sqrt[β]
/. β -> 1 + 2 γ - 56/(3 γ)
/. γ -> (4 Sqrt[4197]/9 - 4)^(1/3)


(if you ever worked with Maple, this is similar to how it formats complex output expressions)

-

## marked as duplicate by Oleksandr R., Michael E2, Sjoerd C. de Vries, Mr.Wizard♦Jun 9 '13 at 1:45

FullSimplify looks like it does a better job. – Spawn1701D Jun 6 '13 at 3:56
You've seen ExperimentalOptimizeExpression? Although it's meant for numerical applications, its job is indeed CSE. – Oleksandr R. Jun 6 '13 at 3:59
@Oleksandr, I think there was a question before that was also answered by ExperimentalOptimizeExpression[]; would you happen to remember it? – J. M. Jun 6 '13 at 4:00
@0x4A4D (25132), (2878), (8787)? More closely related to this question: (9750). – Oleksandr R. Jun 6 '13 at 4:06
@Oleksandr, I had the second one in mind. Thanks! – J. M. Jun 6 '13 at 4:11

I once tried doing something like this myself, and ended up with a semi-manual process.

Clear[branches, tallyBranches];
branches[b_?AtomQ] := {};
branches[b_?NumberQ] := {};
branches[h_[b___]] := Flatten@Append[branches /@ List[b], h[b]];
tallyBranches[e_, k_Integer: 2] :=
TableForm[Reverse /@ Cases[Tally[branches[e]], {_, t_ /; t >= k}]]


Let's take the solution to the cubic as an example:

cube = Solve[a x^3 + b x^2 + c x + d == 0, x];


Generate a table of common branches (with at least 9 occurrences):

tallyBranches[cube, 9]

9   1/a
9   b^2
9   -b^2
9   3 a c
9   -b^2+3 a c
12  b^3
12  -2 b^3
12  9 a b c
12  a^2
12  -27 a^2 d


Then we can manually pick a branch to substitute:

cube2 = cube //. -b^2 + 3 a c -> α;


And then repeat:

tallyBranches[cube2, 6];


Etc..

After three substitutions we end up with something like this:

$$\left\{\left\{x\to -\frac{\sqrt[3]{2} \alpha }{3 a \sqrt[3]{\gamma }}-\frac{b}{3 a}+\frac{\sqrt[3]{\gamma }}{3 \sqrt[3]{2} a}\right\},\left\{x\to \frac{\left(1+i \sqrt{3}\right) \alpha }{3\ 2^{2/3} a \sqrt[3]{\gamma }}-\frac{b}{3 a}-\frac{\left(1-i \sqrt{3}\right) \sqrt[3]{\gamma }}{6 \sqrt[3]{2} a}\right\},\left\{x\to \frac{\left(1-i \sqrt{3}\right) \alpha }{3\ 2^{2/3} a \sqrt[3]{\gamma }}-\frac{b}{3 a}-\frac{\left(1+i \sqrt{3}\right) \sqrt[3]{\gamma }}{6 \sqrt[3]{2} a}\right\}\right\}$$

where $\alpha =3 a c-b^2$, $\beta =-27 a^2 d+9 a b c-2 b^3$, and $\gamma =\sqrt{4 \alpha ^3+\beta ^2}+\beta$.

-