Complex numbers product using only three multiplications
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.
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
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.