Exercise 2.34 introduces Horner's rule, an algorithm for the efficient evaluation of polynomial expressions at a given value of x. Horner's rule evaluates a polynomial expression using the fewest possible number of additions and multiplications.

Let's take a look at a specific example to see how this works.

4x

^{3}+ 3x^{2}+ 2x + 1The terms of the polynomial above can be grouped as follows

(4x

^{3}+ 3x^{2}+ 2x) + 1Once that grouping is in place it's easier to see that you can now factor out an x from the term in parentheses.

x * (4x

^{2}+ 3x + 2) + 1Now you can apply the same grouping and factoring steps to the term left in parentheses.

x * (x * (4x + 3) + 2) + 1

This is as far as we can go because another x cannot be factored out of the term in the innermost parentheses.

More generally, Horner's rule says that the polynomial

a

_{n}x^{n}+ a_{n-1}x^{n-1}+ ... + a_{0}can be evaluated as

((a

_{n}x + a_{n-1})x + ...)x + a_{0}This reduces the total number of multiplications performed because the exponents in each term of the original polynomial are not computed separately.

Using Horner's rule, evaluating polynomials can be formulated as an accumulation. Our task in this exercise is to complete the following implementation, assuming that the coefficients of the polynomial are arranged in a sequence from a

_{0}through a

_{n}.

`(define (horner-eval x coefficient-sequence)`

(accumulate (lambda (this-coeff higher-terms) <??>)

0

coefficient-sequence))

Given the framework and assumption above, there really are not a lot of different ways to go about this. The

`accumulate`

procedure is already doing most of the work for us, recursively accumulating the terms of the polynomial in the order that they're (conveniently) provided. All we have to do is implement the operator function that gets passed to accumulate.The piece that we need to implement is summarized in the text as follows:

In other words, we start with a_{n}, multiply by x, add a_{n-1}, multiply by x, and so on, until we reach a_{0}.

In our lambda, a

_{0}through a

_{n}are represented by

`this-coeff`

, so all we need to do is add `this-coeff`

to the accumulation and multiply by x.`(define (horner-eval x coefficient-sequence)`

(accumulate (lambda (this-coeff higher-terms)

(+ (* x higher-terms) this-coeff))

0

coefficient-sequence))

Here also is the implementation of

`accumulate`

so you can test the `horner-eval`

procedure.`(define (accumulate op initial sequence)`

(if (null? sequence)

initial

(op (car sequence)

(accumulate op initial (cdr sequence)))))

Let's start with a simpler test case than the one provided in the text and add terms so we can more easily predict what the correct output should be. The first example below is evaluating the polynomial (1 + 3x) where x = 2, and the final example is evaluating (1 + 3x + 5x

^{3}+ x

^{5}), also at x = 2.

`> (horner-eval 2 (list 1 3))`

7

> (horner-eval 2 (list 1 3 0))

7

> (horner-eval 2 (list 1 3 0 5))

47

> (horner-eval 2 (list 1 3 0 5 0))

47

> (horner-eval 2 (list 1 3 0 5 0 1))

79

Related:

For an interesting application of Horner's rule, see the solution to Look And Say, Revisited from Programming Praxis.

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

## 3 comments:

Usually you do something from SICP, then I copy it in my blog. But this time I beat you!

pbewig,

Very nice application of Horner's rule. That was only a few days ago too! That should teach me not to get behind on reading my RSS feeds. :)

Very informative post.Thanks for sharing.

Post a Comment