Consider the polynomial p(x) = a0 + a1x + a2x2 + a3x3 , where ai ≠ 0 ∀i. The…
2006
Consider the polynomial p(x) = a0 + a1x + a2x2 + a3x3 , where ai ≠ 0 ∀i. The minimum number of multiplications needed to evaluate p on an input x is:
- A.
3
- B.
4
- C.
6
- D.
9
Attempted by 140 students.
Show answer & explanation
Correct answer: A
Key idea: use Horner's method to minimize multiplications.
Compute a3 * x (1 multiplication).
Add a2 and multiply the result by x: (a3*x + a2) * x (1 multiplication).
Add a1 and multiply the result by x: ((a3*x + a2) * x + a1) * x (1 multiplication).
Finally add a0 (no multiplication).
Multiplication count: 3 (one multiplication in each of the three Horner steps).
Why this is minimal: Horner's method uses exactly one multiplication per decrease in degree when coefficients are nonzero. For a degree-3 polynomial with all coefficients nonzero, you must perform three multiplications to incorporate the x factors up to x^3, so no evaluation can use fewer than 3 multiplications.