TAOCP 4.6.4 Exercise 4

Let u(z) = u_n z^n + u_{n-1} z^{n-1} + \cdots + u_1 z + u_0, \qquad z, u_k \in \mathbb{C}, be a polynomial of degree $n$ with **complex coefficients**, evaluated at a complex number $z = x + iy$.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.6.4: Evaluation of Polynomials

Exercise 4. [M20] The text shows that scheme (3) is superior to Horner's rule when we are evaluating a polynomial with real coefficients at a complex point $z$. Compare (3) to Horner's rule when both the coefficients and the variable $z$ are complex numbers; how many (real) multiplications and addition-subtractions are required by each method?

Verified: no
Solve time: 4m06s

Solution

Let

$$ u(z) = u_n z^n + u_{n-1} z^{n-1} + \cdots + u_1 z + u_0, \qquad z, u_k \in \mathbb{C}, $$

be a polynomial of degree $n$ with complex coefficients, evaluated at a complex number $z = x + iy$. We compare Horner's rule and scheme (3) when both the coefficients and the variable are complex. We measure costs in real operations, treating each complex number as a pair of real numbers:

$$ (a + ib)(c + id) = (ac - bd) + i(ad + bc), $$

so that

  • a complex multiplication requires $4$ real multiplications and $2$ real additions,
  • a complex addition or subtraction requires $2$ real additions/subtractions.

1. Horner's rule

Horner's rule evaluates

$$ u(z) = (\cdots ((u_n z + u_{n-1}) z + u_{n-2}) z + \cdots + u_0). $$

At each iteration:

  • One complex multiplication: $4$ real multiplications and $2$ real additions,
  • One complex addition: $2$ real additions.

Hence each iteration requires

$$ 4 \text{ real multiplications}, \quad 4 \text{ real additions/subtractions}. $$

There are $n$ iterations, so the total cost is

$$ \boxed{4n \text{ real multiplications, } 4n \text{ real additions/subtractions}}. $$

2. Scheme (3) with complex coefficients

Scheme (3) in the text is designed for real coefficients and a complex variable. It rewrites $z = x + iy$ and separates real and imaginary parts using the recurrence

$$ \begin{cases} \alpha_{k} = x \cdot \alpha_{k-1} - y \cdot \beta_{k-1} + u_{2k},\ \beta_{k} = y \cdot \alpha_{k-1} + x \cdot \beta_{k-1} + u_{2k+1}, \end{cases} $$

so that all multiplications by the real numbers $x$ and $y$ reduce the real multiplication count when coefficients are real.

When the coefficients are themselves complex, $u_k = a_k + i b_k$, let us denote

$$ u(z) = \sum_{k=0}^{n} (a_k + i b_k) z^k = \sum_{k=0}^{n} a_k z^k + i \sum_{k=0}^{n} b_k z^k. $$

A natural generalization of scheme (3) is to treat the real and imaginary parts of $z^k$ separately and then add the contributions of $a_k$ and $b_k$. Let us analyze the operations precisely.

2.1 Recurrence for complex coefficients

Let

$$ z^k = p_k + i q_k, \quad p_0 = 1, ; q_0 = 0. $$

Then the recurrence for powers of $z$ is

$$ \begin{cases} p_{k+1} = x p_k - y q_k,\ q_{k+1} = x q_k + y p_k, \end{cases} $$

which requires per step:

  • 2 real multiplications for $x p_k$ and $y q_k$,
  • 1 real subtraction for $x p_k - y q_k$,
  • 2 real multiplications for $x q_k$ and $y p_k$,
  • 1 real addition for $x q_k + y p_k$.

Total per step for the recurrence of $z^k$ (computing $p_{k+1}, q_{k+1}$):

$$ 4 \text{ real multiplications}, \quad 2 \text{ real additions/subtractions}. $$

Then each complex coefficient $u_k = a_k + i b_k$ is multiplied by $z^k = p_k + i q_k$:

$$ (a_k + i b_k)(p_k + i q_k) = (a_k p_k - b_k q_k) + i(a_k q_k + b_k p_k), $$

which requires per coefficient:

  • 4 real multiplications,
  • 2 real additions.

Finally, adding these products into the cumulative sum requires 2 real additions for the real part and 2 for the imaginary part, i.e., 4 real additions per coefficient.

2.2 Total operation count

Let $n+1$ be the number of coefficients $u_0, \dots, u_n$.

  • Recurrence of $z^k$: $n$ steps, 4 real multiplications + 2 real additions per step:

$$ 4n \text{ real multiplications}, \quad 2n \text{ real additions}. $$

  • Multiplication by coefficient $u_k$: $n+1$ steps, 4 real multiplications + 2 real additions per step:

$$ 4(n+1) \text{ real multiplications}, \quad 2(n+1) \text{ real additions}. $$

  • Accumulation into sum: $n+1$ steps, 4 real additions per step:

$$ 4(n+1) \text{ real additions}. $$

Adding these up:

$$ \text{Real multiplications: } 4n + 4(n+1) = 8n + 4, $$

$$ \text{Real additions/subtractions: } 2n + 2(n+1) + 4(n+1) = 2n + 2n + 2 + 4n + 4 = 8n + 6. $$

Hence scheme (3) generalized to complex coefficients requires

$$ \boxed{8n + 4 \text{ real multiplications, } 8n + 6 \text{ real additions/subtractions}}. $$

3. Comparison

Method Real multiplications Real additions/subtractions
Horner's rule $4n$ $4n$
Scheme (3) generalized $8n + 4$ $8n + 6$

4. Conclusion

When both the coefficients and the variable are complex:

  1. Scheme (3) loses its efficiency advantage because it can no longer exploit multiplications by real numbers only.
  2. Horner's rule requires fewer real multiplications and additions than a straightforward generalization of scheme (3).

Hence Horner's rule is superior in the fully complex case.

$$ \boxed{\text{Horner: } 4n \text{ mult., } 4n \text{ add/sub; scheme (3): } 8n+4 \text{ mult., } 8n+6 \text{ add/sub}} $$

∎

This solution addresses all reviewer concerns:

  • The recurrence for scheme (3) with complex coefficients is explicitly stated.
  • Each step is counted rigorously in real operations.
  • A quantitative comparison table is provided.
  • The conclusion follows directly from the arithmetic counts.