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 6 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 RISC-V 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{.}\) We use register a0 to hold the accumulator \(r\) and initialize it 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:
mv t1, a0
li a0, 0
j horner_head
horner_loop:
lw t0, 0(t1)
mul a0, a0, a2
add a0, a0, t0
addi t1, t1, 4
horner_head:
bne t1, a1, horner_loop
ret
tail recursive means that the recursive invocation of a function is the result of the function and is not used in further calculations.
