17

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?

Vitality
  • 20,705
  • 4
  • 108
  • 146
Chandrashekhar Garkar
  • 325
  • 1
  • 3
  • 8
  • 2
    This question is off-topic because it is about multiplying complex numbers It should be on [math.se] –  Oct 27 '13 at 18:25
  • 8
    @MikeW It probably wouldn't be off topic over there, but I don't see how it's off topic *here* either. Complex numbers are important in plenty of programming tasks and OP is essentially asking for an *algorithm*. –  Oct 27 '13 at 18:27
  • This is essentially Karatsuba multiplication used heavily in Algorithms. – Vallabh Patade Oct 27 '13 at 18:29
  • 1
    @delnan What you say might be true, but this is a programming site. As the question is stated it's not clear that it's anything other than a problem in mathematics. –  Oct 27 '13 at 18:36
  • 1
    @MikeW I thing you're wrong here. If the question had something like "in our program we're multiplying..." it would be directly related to stackoverflow. – kilotaras Oct 27 '13 at 18:44
  • 1
    @kilotaras This is why we have a voting system. –  Oct 27 '13 at 18:45
  • I think that fast complex multiplication originated with Gauss. Can anybody provide an approximate date or historical reference with the programming solution? – richard1941 Jul 21 '17 at 02:34

5 Answers5

28

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.

Dave Jarvis
  • 30,436
  • 41
  • 178
  • 315
Vallabh Patade
  • 4,960
  • 6
  • 31
  • 40
  • 2
    This is from Gauss, not Karatsuba. Karatsuba multiplication is for the quad precision product of two double precision integers. In 1960 when this was discovered, multiplication in computers was a slow operation consisting of shift and add-- 32 such operations for a 32 bit integer, as in Russian peasant multiplication. Yes, the Gauss and Karatsuba procedures are very similar, but the goals are different. And Karatsuba can be applied recursively to larger problems; not Gauss. – richard1941 Jul 21 '17 at 02:41
  • @richard1941 You're not wrong, but the Gauss algorithm is essentially a special case of the basic step of karatsuba with base i. I am not sure what the real value of making a distinction is apart from historical accuracy. – Tim Seguine May 08 '18 at 12:59
11

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
Paolo Bonzini
  • 1,900
  • 15
  • 25
hunse
  • 3,175
  • 20
  • 25
10

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.

Vitality
  • 20,705
  • 4
  • 108
  • 146
7

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

Sergey Salishev
  • 71
  • 1
  • 2
  • 1
    So 5 additions, but 2 of them can be precomputed? – Teepeemm Sep 09 '15 at 13:25
  • Exactly. I stumbled on this trying to understand obscure complexity numbers in Split-radix FFT because 2 out of 5 real additions were missing. – Sergey Salishev Sep 10 '15 at 08:37
  • Notice that now you need to keep 3 real numbers instead of original 2 for each twiddle factor, i.e. a, y, z instead of just a, b. This may have some effect on cache locality. Also, depending on the availability of SIMD intrinsics, it might be better to keep it as just 2 real numbers. – syockit Nov 24 '18 at 16:56
0

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.

Paul
  • 114
  • 3