Converting Mathematica Expressions to C
with Common Subexpression Elimination

I frequently use Mathematica to rearrange or solve symbolic equations to use in C++ programs. While Mathematica is quite powerful for that, it has no facility to hoist common subexpressions into variables. This code does that.

Example to convert

This calculates a closed-form symbolic solution to the problem of finding the affine transform that would turn triangle1 into triangle2. The details are relatively unimportant, but the symbolicSolution output is clearly unusable directly in C. We want to hoist out all the common parts as separate calculations, saving the values in variables.

Creates the matrices and triangles

Converting To C with CSE_1.gif

Solves for the affine transform. This variable is used below as test data

Converting To C with CSE_2.gif

Converting To C with CSE_3.gif

Conversion code

This code does the conversion. While I haven't tested it on many problems, it seems likely to be generally useful.

Returns a list of all the non-atomic subexpressions in the original expression. The list is sorted so that smaller subexpressions come first, producing a bottom-up search and replacement of the common subexpressions

Converting To C with CSE_4.gif

The workhorse function. For each subexpression, if the rest of the subexpressions contain instances of the subexpression, accumulate a rule replacing the subexpression with a variable name (symbol). Note that for clarity, no effort is made to avoid symbols with existing values. The result is a list of the original expression with variables substituted for the common parts, and a list of the replacement rules.

Converting To C with CSE_5.gif

The result can have unnecessary variables, used in only one place, so this function removes them by replacing single-use variables by their definitions.

Converting To C with CSE_6.gif

After folding, rename variables so that they're sequentially numbered. Just for prettyness. Note that these variables use a different prefix to avoid mapping collisions. As before, be sure that no variables named v00, etc. have values.

Converting To C with CSE_7.gif

Combining the above into a single function

Converting To C with CSE_8.gif

Evaluating the result

This is a computation cost function. I've WAG'd the addition, multiplication, and division (power) costs.

Converting To C with CSE_9.gif

Mathematica has a bunch of built-in symbolic restructuring functions. Here we try most of them to see which one produces the result with the least computation cost.

Converting To C with CSE_10.gif

Converting To C with CSE_11.gif

Factor, Together, and Cancel all produce the lowest cost

Compare to the original, unhoisted expression. We've achieved better than a 2x (WAG'd) reduction. Of course, a decent compiler may do just as good, but this will be more readable and manipulable as C source

Converting To C with CSE_12.gif

Converting To C with CSE_13.gif

Apply to our test data to get the compressed expression

Converting To C with CSE_14.gif

Converting To C with CSE_15.gif

Output to C

These functions pick apart the compressed expression and rewrite it as C. This is specific to my original problem, so for other uses, changes will need to be made here

Converting To C with CSE_16.gif

The final output, to be copy/pasted into the C file and tweaked as needed. Note that CForm is somewhat verbose about negations. I have not felt the need to rewrite CForm to fix that.

Converting To C with CSE_17.gif

Converting To C with CSE_18.gif

Spikey Created with Wolfram Mathematica 7.0