# Multiplying two complex numbers using only three multiplications of real numbers

I have problem given below.

Show how two complex numbers $(a+ib)$ and $(c+id)$ may be multiplied using only three multiplications of real numbers, where $i=\sqrt{-1}$. You may use any number of additions and subtractions.

• – lab bhattacharjee Aug 11 '13 at 15:30
• I've improved your question's formatting; apologies if I changed your meaning. You can see here how I edited your question. Please see here for a guide to writing math with MathJax, and see here for a guide to formatting posts with Markdown. – Zev Chonoles Aug 11 '13 at 15:31
• @labbhattacharjee . may i know what is the significance behind this property ? why is this separately emphasized ? – Harish Kayarohanam Aug 11 '13 at 15:33
• @HarishKayarohanam, all I know is available in the link:) – lab bhattacharjee Aug 11 '13 at 15:48
• Ya . @Prahlad Vaidyanathan gave the solution to my question . en.wikipedia.org/wiki/Karatsuba_algorithm – Harish Kayarohanam Aug 11 '13 at 15:52

You are interested in two numbers : $\alpha_1 = ac-bd \text{ and } \alpha_2 = ad+bc$. You can compute 3 products, viz. $P_1 = ac, P_2 = bd, \text{ and } P_3 = (a+b)(c+d)$. Then $\alpha_1 = P_1 - P_2, \text{ and } \alpha_2 = P_3 - P_2 - P_1$.

This process is often called Karatsuba multiplication, and is used in algorithm design quite frequently.

• Simply amazing explanation . Are there any other interesting algorithms like karatsuba algorithm en.wikipedia.org/wiki/Karatsuba_algorithm . Can you direct me to good sources for such algorithms that improves algorithm design ? – Harish Kayarohanam Aug 11 '13 at 15:56
• I am no expert, but there are plenty of books out there for Algorithm design : 1) Sedgewick and Wayne, 2) Kleinberg and Tardos are two that I have looked at. – Prahlad Vaidyanathan Aug 11 '13 at 16:00
• If you are interested in other examples of this kind of phenomenon where you can reduce the number of multiplications at the expense of more additions/subtractions, you can also look up en.wikipedia.org/wiki/Strassen_algorithm to see a similar trick for matrix multiplication. – user2566092 Aug 11 '13 at 16:33
• If you define $P_3 = (a - b)(d - c)$, then $a_2 = P_3 - a_1$, which also saves some computation. – sukhmel May 29 '14 at 22:18
• @sukhmel It's wrong .since $P3 = ad - bd - ac + bc ,P3 - \alpha_1 = ad-2ac+bc$ – john Feb 2 '15 at 14:22

Prahlad Vaidyanathan has already answered on how performing the product between two complex numbers with only three real multiplications. Now the question is: can we perform the product between two complex numbers with less than three real multiplications?

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