Skip to main content

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
Run
tail recursive means that the recursive invocation of a function is the result of the function and is not used in further calculations.