Section 3.4 Evaluating 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:
b horner_head
horner_loop:
lw $t0 ($a0)
mulu $v0 $v0 $a2
addu $v0 $v0 $t0
addiu $a0 $a0 4
horner_head:
bne $a0 $a1 horner_loop
jr $ra
tail recursive means that the recursive invocation of a function is the result of the function and is not used in further calculations.
