Arithmetic Expression Calculation Optimization Algorithm

Question

Suppose I have an expression formed by integer variables and arithmetic operations: addition, subtraction and multiplication. I know that each multiplication takes M seconds, and each addition / substitution takes A seconds. Is there an algorithm that will evaluate an expression in the most efficient way for arbitrary assignment to variables? (Suppose I can only store one number in memory).

Example:

M = 10

A = 1

Expression: a * a + a * b + b * b.

Initially, it has 3 multiplications and 2 additions, so the total time is 3 * M + 2 * A = 32

However, we can construct the equivalent expression (a + b) * (a + b) -a * b, which has only 2 multiplications and 3 additions, so the total calculation time will be 2 * M + 3 * A = 23.

Answer 1

You want to apply the sum product algorithm.

Cm:

http://www.isiweb.ee.ethz.ch/papers/docu/aloe-2001-1.pdf

Answer 2

Basically you want to reduce the number of multiplications. One approach is as follows (I don't know if the cost reduction justifies the complexity algorithm and the cost of the algorithm):

• Adding Perfom for all operands for which addition is allowed according to the priority of the operator.

• Form pairs of operands to be multiplied.

• Among the pairs, take out the common operands and add them together.

• Update the pairs and go to step 3.

• Stop if there are no such common pairs left. Then just do the rest of the calculations.

  Example: a * b + a * c + d * (e + f) complement the e and f (say g = e + f) a * b + a * c + d * g pairs: (a, b) (a, c) (d, g) a is common in the 1st two pairs, so we add b and c.