Editing Multiplication algorithm (section)

==Complex number multiplication==
Complex multiplication normally involves four multiplications and two additions.

:<math>(a+bi) (c+di) = (ac-bd) + (bc+ad)i.</math>

Or

:<math>
\begin{array}{c|c|c}
\times & a & bi \\
\hline
c & ac & bci \\
\hline
di & adi & -bd
\end{array}
</math>

As observed by Peter Ungar in 1963, one can reduce the number of multiplications to three, using essentially the same computation as [[Karatsuba's algorithm]].<ref name="taocp-vol2-sec464-ex41">{{Citation | last1=Knuth | first1=Donald E. | author1-link=Donald Knuth | title=The Art of Computer Programming volume 2: Seminumerical algorithms | publisher=[[Addison-Wesley]] | year=1988 | pages=519, 706| title-link=The Art of Computer Programming }}
</ref> The product (''a''&nbsp;+&nbsp;''bi'') · (''c''&nbsp;+&nbsp;''di'') can be calculated in the following way.

:''k''<sub>1</sub> = ''c'' · (''a'' + ''b'')
:''k''<sub>2</sub> = ''a'' · (''d'' − ''c'')
:''k''<sub>3</sub> = ''b'' · (''c'' + ''d'')
:Real part = ''k''<sub>1</sub> − ''k''<sub>3</sub>
:Imaginary part  = ''k''<sub>1</sub> + ''k''<sub>2</sub>.

This algorithm uses only three multiplications, rather than four, and five additions or subtractions rather than two. If a multiply is more expensive than three adds or subtracts, as when calculating by hand, then there is a gain in speed. On modern computers a multiply and an add can take about the same time so there may be no speed gain. There is a trade-off in that there may be some loss of precision when using floating point.

For [[fast Fourier transform]]s (FFTs) (or any [[Linear map|linear transformation]]) the complex multiplies are by constant coefficients ''c''&nbsp;+&nbsp;''di'' (called [[twiddle factor]]s in FFTs), in which case two of the additions (''d''−''c'' and ''c''+''d'') can be precomputed. Hence, only three multiplies and three adds are required.<ref>{{cite journal |first1=P. |last1=Duhamel |first2=M. |last2=Vetterli |title=Fast Fourier transforms: A tutorial review and a state of the art |journal=Signal Processing |volume=19 |issue=4 |pages=259–299 See Section 4.1 |date=1990 |doi=10.1016/0165-1684(90)90158-U |bibcode=1990SigPr..19..259D |url=https://core.ac.uk/download/pdf/147907050.pdf}}</ref>  However, trading off a multiplication for an addition in this way may no longer be beneficial with modern [[floating-point unit]]s.<ref>{{cite journal |first1=S.G. |last1=Johnson |first2=M. |last2=Frigo |title=A modified split-radix FFT with fewer arithmetic operations |journal=IEEE Trans. Signal Process. |volume=55 |issue= 1|pages=111–9 See Section IV  |date=2007 |doi=10.1109/TSP.2006.882087 |bibcode=2007ITSP...55..111J |s2cid=14772428 |url=https://www.fftw.org/newsplit.pdf }}</ref>