🚀 go-pugleaf

In article <3532@epimass.EPI.COM> jbuck@epimass.EPI.COM (Joe Buck) writes:
:In article <121828@sun.Eng.Sun.COM> rtrauben@sun.UUCP (Richard Trauben) writes:
:>The "current/previous" generation of ATT and Texas Instruments digital 
:>signal processor (DSP) chips provide complex floating point arithmetic
:>primitives to speed up the inner-loop multiply/accumulate butterfly 
:>operation of a fast fourier transform.
:
:There is no support for complex arithmetic per se in the TI TMS320
:family, and I don't believe there is any in the AT&T chips either.
:What is supported is a magic "bit reversal addressing" mode, which
:makes it easy to handle the shuffling operation required in an FFT.
:
:It requires four multiplies, an addition, and a subtraction to do a
:complex multiply; you can do this in four cycles on the TMS320C30 by
:taking advantage of parallel multiplication and addition/subtraction.
 
This is not quite correct. Usually [on most hardware] multiplies take
significantly longer than additions. Two complex numbers can be
multiplied in THREE multiplications (not four) at the expense of a 
couple extra add/subtracts:

(a+bi)(c+di) = ac - bd + ((a+b)(c+d) - ac -bd) i

One computes a+b and c+d , then does 3 multiplications: ac, bd and (a+b)(c+d)
one additional add, and 3 subtracts finishes it.

Total: 3 multiplies, 3 adds, 3 subtracts. This can be faster depending
on the relative speed of multiplication and addition. It is almost
always faster if working in double precision.

Bob Silverman