8
$\begingroup$

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.

(original image)

Please help me. How to solve this?

$\endgroup$
16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Harish Kayarohanam Aug 11 '13 at 15:56
  • 1
    $\begingroup$ 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. $\endgroup$ – Prahlad Vaidyanathan Aug 11 '13 at 16:00
  • $\begingroup$ 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. $\endgroup$ – user2566092 Aug 11 '13 at 16:33
  • $\begingroup$ If you define $P_3 = (a - b)(d - c)$, then $a_2 = P_3 - a_1$, which also saves some computation. $\endgroup$ – sukhmel May 29 '14 at 22:18
  • $\begingroup$ @sukhmel It's wrong .since $P3 = ad - bd - ac + bc ,P3 - \alpha_1 = ad-2ac+bc$ $\endgroup$ – john Feb 2 '15 at 14:22
1
$\begingroup$

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?

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.