The paper showing that quaternion product requires 7 multiplications is: home.pipeline.com/~hbaker1/quaternion/cornellcstr75-245.ps.gz I think Knuth Vol II shows the basic outline of these types of proofs. As you can imagine, anything having to do with signal processing has been optimized like crazy, so things like complex products have been covered, as well as all kinds of real & complex polynomial products. With today's processors, it isn't clear that any of these tricks help, and probably actually hurt, since (pipelined) floating point operations are more or less "free", relative to memory access operations. You might check out the work of V. Pan, who has done a lot of work on things like FFT optimizations. At 03:23 PM 8/1/2007, Richard Schroeppel wrote:

I'm looking for a hypothetical review article that I hope someone has written for me:

It contains a summary of computing costs for various optimal algorithms ...

Multiplying complex numbers takes 3 real multiplications. Multiplying quaternions takes 7 real multiplications. etc.

Rich