This was a problem done in my CIS 315 Algorithms class in Spring 2006.
The product of two linear polynomials ax+b and cx+d
(ax+b)(cx+d)
is
acx^2 + (ad+bc)x + bd
Note that this requires 4 different multiplications of the coefficients: ac, ad, bc and bd.
We want to find a way to determine this product with only 3 multiplications.
let:
L = (a+b)(c+d)
note what happens when we FOIL L:
L = ac + ad + bc + bd
We think that maybe we can combine the middle term (ad+bc) with only one multiplication. What we want is ad + bc, so subtract ac and bd from L:
J = ac
K = bd
L - J - K = (ac + ad + bc + bd) - ac - bd
Note at this point we can rewrite the original FOILed product as:
Jx^2 + (L - J - K)x + K
We now have solved the problem with only 3 multiplications. They are:
J, K and L, or ac, bd, and (a+b)(c+d)
