Reduce the number of operations on a simple expression

Question

Lets say I take a computation that involves only addition and multiplication:

(a+b)*(c+d)

which can be done in many other ways, eg.

a*(c+d) + b*(c+d)
a*c + a*d + b*c + b*d

In terms of additions and multiplications the number of operations required for each of the three examples shown are (2,1) (3,2) (3,4) respectively. Clearly, if the goal is to reduce the total number of operations the first is superior. Is there a way, given an arbitrary expression to find the computation order that requires the least number of operations?

Note: This question is being re-asked from SE.math for the insight and perspective of the CS crowd.

Answer 1

What you want is to effectively generate all possible equivalent algebraic expressions, and choose the one that takes the least costly number of steps (adding X three times is cheaper on most machines than multiplying X by 3).

It is impractical to do this, as the number of "equivalent" formulas is infinite.

However, Pelegrí-Llopart figured out a scheme to generate optimal code given a fixed number of algebraic rewrite rules, called "BURS" (bottom-up rewrite system). This has been implemented in some code generators.

In essence, he constructs offline a big automata whose states track the set of possible applied rewrites. Each state knows what to generate when it occurs, so the online time for code generation is cheap.