## Section3.4Evaluating Polynomials with Horner's Method

Horner's method is a technique to evaluate a polynomial

\begin{equation*} p(x)=a_0+a_1x+\cdots+a_nx^n \end{equation*}

for some value $$x\text{.}$$ When implementing this formula in a computer program in the straightforward way, we need $$1+\cdots+n-1$$ multiplications for all the different powers of $$x\text{.}$$ A more efficient imperative implementation could of course memorize the “last” power $$x^{i-1}$$ of $$x$$ and compute $$x^i$$ by $$x\cdot x^{i-1}\text{.}$$ This would then require two multiplications per summand: one to compute $$x^i$$ and one for $$a_ix^i\text{.}$$

In contrast, Horner's method evaluates the polynomial with $$n$$ multiplications. It relies on successively factoring out $$x$$ in the term above, giving:

\begin{equation*} p(x)=a_0+x(a_1+\cdots +x(a_{n-2}+x(a_{n-1}+a_nx)\cdots)) \end{equation*}

This becomes more palpable when written down using tail-recursive  7  equations:

\begin{align*} p'(x,0,r) \amp = r\cdot x + a_0\\ p'(x,i,r) \amp = p'(x, i-1, r\cdot x + a_i)\text{ for }i>0 \end{align*}

with

\begin{equation*} p(x)=p'(x, n, 0) \end{equation*}

The following MIPS program implements this tail-recursive scheme using a simple loop (and no function calls). The function horner accepts three parameters: A pointer to the begin and end of the coefficient array and $$x\text{.}$$ Register $v0 is provisioned to hold the accumulator $$r$$ and is initialized to $$a_n\text{,}$$ the first element in the coefficient array. In each iteration of the loop, the accumulator is multiplied by $$x$$ and added to $$a_{i}\text{.}$$  .text .globl horner #$a0 Coefficients base
# $a1 Coefficients end #$a2 x
horner:
lw     $t0 ($a0)
mulu   $v0$v0 $a2 addu$v0 $v0$t0
addiu  $a0$a0 4
bne    $a0$a1 horner_loop