Reducing Multiplications in a Set of Equations

Question

I have two equations:

x = ab + bc + ad - cc

y = ab + cc + cd

In these two equations combined, there is a cost of seven multiplications. I want to reduce this number down to three. I can do this, for example, by setting a temporary variable, called temp1 and set it to the value cc. Now, my set of equations will look like this:

x = ab + bc + ad - temp1

and

y = ab + temp1 + cd

This updated set of equations now has a cost of six multiplications.

I have started by setting temp1 to ab and using the distributive law with bc and cc, which can reduce the cost down to four multiplications, but I get stuck here:

x = ad + c(b - c) + temp1

y = temp1 + c(c + d)

What other factors, temporary variables, or additions/subtractions can I take from these two sets of equations to reduce the cost down to three?

Answer 1

I need to find a common factor between x and y to serve as the temporary variable. ab and cc are common, but cd is not. So, I will add and subtract cd to x:

x = ab + bc + ad - cc + cd - cd

x = ab + ad + c(b+d) - c(c+d)

x = a(b+d) + c(b+d) - c(c+d)

x = (b+d)(a+c) - c(c+d)

Now, we can assign a temporary variable: tmp1 = c(c + d) and use it in both x and y.

x = (b+d)(a+c) - tmp1

y= ab + tmp1

which only uses three multiplications.