Ames Laboratory, Department of Energy, ISU, Ames, Iowa

Complex Product

We have already mentioned the trick for computing the product of complex numbers (a + ib) and (c + id) with only three multiplications. The search program found 12 different ways of doing this, two of which are given below:

m1 = c (a - b)	m1 = (a - b) (c + d)
m2 = d (a + b)	m2 = b c
m3 = b (c - d)	m3 = a d
u = m1 m3	u = m1 m2 m3
v = m2 m3	v = m2 m3

An exhaustive search with a budget of three multiplications and five adds took 21 hours and 10 minutes on a 256-processor nCUBE 2. This represents approximately 10¹⁴ integer operations. Reduction of the budget to four adds revealed no way to compute the goal expressions ac bd and ad bc, providing a computational 'proof' of the nonexistence of a method with fewer adds.

Aggressive pruning rules can be used to reduce the search time: expressions involving ab or cd are disallowed, as are expressions involving sums , , , or (aggressive pruning rule 4). Non-homogeneous expressions, expressions with degree higher than two (highest degree among goal expressions) and expressions having terms with coefficients other than (see Section 6) are disallowed. Although we have no proof that optimal methods cannot use such steps, we empirically observed the efficacy of these pruning rules and make use of them in related problems such as cross product and matrix-matrix product. For the complex product, a search with the aggressive pruning rules took only 0.18 seconds on a 64-processor nCUBE, yet found all 12 methods. Aggressive pruning rules destroy proof of optimality, but speed the discovery of new methods. Without aggressive pruning rules, the method that forms the alternative title of this paper would probably not have been tractable with current high-speed computers.