SICP 2.34: Horner's rule

From SICP section 2.2.3 Sequences as Conventional Interfaces

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³ + 3x² + 2x + 1

The terms of the polynomial above can be grouped as follows

(4x³ + 3x² + 2x) + 1

Once 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² + 3x + 2) + 1

Now 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_nxⁿ + a_n-1x^n-1 + ... + a₀

can be evaluated as

((a_nx + a_n-1)x + ...)x + a₀

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₀ 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₀.

In our lambda, a₀ 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³ + x⁵), 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.