CODEWITHSUNDEEP
algorithmoptimizationexpression
Evgenii.Balai
Evgenii.Balai

Reputation: 949

Algorithm for optimizing computation of an arithmetic expression

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/substraction takes A seconds. Is there an algorithm which will compute the expression in the most efficient way for an arbitrary assignment to the variables? (Assume I can store in memory only one number).

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 build an equivalent expression (a+b)*(a+b)-a*b which has only 2 multiplications and 3 additions, so the total computation time will be 2*M+3*A=23.

Upvotes: 4

Views: 583

Answers (2)

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

You basically want to reduce the number of multiplications. One approach is the following (i don't know whether the resulting cost reduction shall justify the algorithm complexity and cost):

  1. Perfom addition on all operands for which addition is allowed as per operator precedence.

  2. Form pairs of operands that have to undergo multiplication.

  3. Among the pairs, take out the common operands and add their counterparts together.

  4. Update the pairs and goto step 3.

  5. Stop when no such common pairs are left. Then just do the remaining calculation.

    Ex: a*b + a*c + d*(e+f) perform addition on e & 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 & c.

Upvotes: 1

Owen
Owen

Reputation: 1736

You want to apply the sum product algorithm.

See:

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

Upvotes: 1

Related Questions