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

Cross Product

Among many applications, computer graphics uses the cross product of three-vectors extensively to determine intersections of rays and polygons or to create plane normals. The conventional algorithm is as follows:

Given three vectors and ,
find

a₂ b₃ a₃ b₂ ,
a₃ b₁ a₁ b₃ ,

as the three goal expressions.

While working on a synthetic scene generation program, we wondered if there might be a way to compute a cross product in less than six multiplications, at the cost of extra adds. The Sandia nCUBE 2, with 1,024 total processors, was invaluable for this search; we used 256 of its processors for a period of 5 hours and 40 minutes and discovered the method with the first set of stems distributed by the master. A search that went through all the stems would have taken a month, even with aggressive pruning rules. The method is shown at the end of Section 1. We believe this is the first publication of the method.