Complex numbers product using only three multiplications

algorithm math complex-numbers
Chandrashekhar Garkar picture Chandrashekhar Garkar · Oct 27, 2013 · Viewed 10.3k times · Source

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

Vallabh Patade picture Vallabh Patade · Oct 27, 2013

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.

Related questions

What's a nice method to factor gaussian integers?

I already have prime factorization (for integers), but now I want to implement it for gaussian integers but how should I do it? thanks!

Read More
Calculate distance between two latitude-longitude points? (Haversine formula)

How do I calculate the distance between two points specified by latitude and longitude? For clarification, I'd like the distance in kilometers; the points use the WGS84 system and I'd like to understand the relative accuracies of the approaches available.

Read More
Unfamiliar symbol in algorithm: what does ∀ mean?

I'm reading about an algorithm (it's a path-finding algorithm based on A*), and it contains a mathematical symbol I'm unfamiliar with: ∀ Here is the context: v(s) ≥ g(s) = mins'∈pred(s)(v(s') + c(s', s)) ∀s ≠ sstart Can …

Read More