Complex numbers product using only three multiplic

Question

We do complex number multiplication as follows:

(a + i * b) * (c + i * d) = (a * c - b * d) + i * (a * d + b * c)

The real and imaginary parts of the result are

real part = (a * c - b * d)
imag part = (a * d + b * c)

This involves four real multiplications. How can we do it with only three real multiplications?

Answer 1

Some algorithms, e.g. Split-radix FFT set higher expectations on complex multiplication requiring complexity of exactly 3 real multiplications and 3 real additions.

(a+ib)(c+id)=ac−bd+i(ad+bc)    

x=a(c−d)
y=a+b
z=a−b
ac-bd=zd+x
ad+bc=yc−x

In an FFT, y and z come entirely from the twiddle factors, so they can be precomputed and stored in a look-up table. So the requirement is fulfilled. FFT Tricks

Answer 2

Vallabh Patade has already answered on how performing the product between two complex numbers with only three real multiplications. The application of Karatsuba's algorithm is indeed the following

x = a + i * b;
y = c + i * d;

real(x * y) = a * c - b * d;
imag(x * y) = (a + b) * (c + d) - a * c - b * d;

Now the question is: can we perform the product between two complex numbers with less than three real multiplications?

The answer is NO and is provided by Winograd's theorem in

S. Winograd, "On the number of multiplications required to compute certain functions", Commun. Pure Appl. Math. 23 (1970), 165-179.

The minimum number of multiplications required in the computation of the product between two complex numbers is three.

Answer 3

For completeness, I'd like to point out Gauss' complex multiplication algorithm, which is another way to do complex multiplication with only three multiplies. To summarize, you compute

k1 = c * (a + b)
k2 = a * (d - c)
k3 = b * (c + d)
Real part = k1 - k3
Imaginary part = k1 + k2

Answer 4

You are interested in two numbers : A=ac−bd and B=ad+bc. Compute three real multiplications S1=ac, S2=bd, and S3=(a+b)(c+d). Now you can compute the results as A=S1−S2 and B=S3−S1−S2.

This process is called Karatsuba multiplication and used heavily in Algorithm analysis.

It is used to find the closest pair of points.