The horner

Computer Science Level 3

What is the minimum number of arithmetic operations required to evaluate the polynomial:

$x^{7}+3x^{5}+4x+8$

for a given value of $x$ with only one temporary variable?

1 solution

Lu Chee Ket
Dec 1, 2015

With only one temporary variable allowed such as x but not x2 and x4:

$((x*x+3)*x*x*x*x+4)*x+8$ required 6 *'s and 3 +'s of total 9 arithmetic operations.

EXP and LN shall require more. But if x2 or x4 are allowed, then we could have:

x2:=x*x or SQR(x);

x4:=x2*x2 or SQR(x2);

$((x2+3)*x4+4)*x+8$ required 4 *'s and 3 +'s of total only 7 arithmetic operations.

Answer: $\boxed{9}$