CODEWITHSUNDEEP
algorithmmathcomplex-numbers
Chandrashekhar Garkar
Chandrashekhar Garkar

Reputation: 335

Complex numbers product using only three multiplications

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?

Upvotes: 18

Views: 19411

Answers (5)

Paul
Paul

Reputation: 144

Winograd is practically correct if you want to do a mixture of adds and multiplies. But if you only want to do complex multiplies, work in logpolar representation that multiplication is just adding logamplitudes and angles; but of course logpolar adds are hard! Logpolar can be nice for limited precision FFTs on e.g. 8 bit logamplitude +j8 bit phase on microprocessors.

Upvotes: 0

Vallabh Patade
Vallabh Patade

Reputation: 5110

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.

Upvotes: 29

hunse
hunse

Reputation: 3255

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

Upvotes: 12

Vitality
Vitality

Reputation: 21475

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.

Upvotes: 10

Sergey Salishev
Sergey Salishev

Reputation: 81

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

Upvotes: 8

Related Questions