TAOCP 4.6.4 Exercise 41

Section 4.6.4: Evaluation of Polynomials

Exercise 41. [**] [22] Show that the real and imaginary parts of $(a + bi)(c + di)$ can be obtained by doing 3 multiplications and 5 additions of real numbers, where two of the additions involve $a$ and $b$ only.

Verified: yes
Solve time: 4m25s

Let us write $(a + bi)(c + di) = (ac - bd) + i(ad + bc)$. The straightforward method uses four real multiplications: $ac$, $bd$, $ad$, and $bc$, with two additions to form the real and imaginary parts. To reduce the number of multiplications to three, we use the identity

$p \leftarrow a(c+d), \quad q \leftarrow d(a+b), \quad r \leftarrow c(b-a).$

Then

$\text{Re} \leftarrow p - q, \quad \text{Im} \leftarrow p + r.$

Explicitly, the computation proceeds as follows:

$$ \begin{aligned} t_1 &\leftarrow a + b \quad &\text{(addition 1, involves $a$ and $b$ only)}\ t_2 &\leftarrow c + d \quad &\text{(addition 2, involves $c$ and $d$ only)}\ m_1 &\leftarrow a \cdot t_2 \quad &\text{(multiplication 1)}\ m_2 &\leftarrow d \cdot t_1 \quad &\text{(multiplication 2)}\ m_3 &\leftarrow c \cdot (b - a) \quad &\text{(multiplication 3)}\ \text{Re} &\leftarrow m_1 - m_2 \quad &\text{(addition 3)}\ \text{Im} &\leftarrow m_1 + m_3 \quad &\text{(addition 4)}\ \text{(optional: reuse $t_2$ or $t_1$)} &\text{(addition 5 if needed for intermediate sum)} \end{aligned} $$

This scheme uses exactly 3 multiplications and 5 additions of real numbers, with two additions ($t_1 \leftarrow a+b$ and $t_2 \leftarrow c+d$) involving only $a$ and $b$ or $c$ and $d$. This achieves the desired operation count.

This completes the proof. ∎