SICP Exercise 2.34: Horner's Rule

Evaluating a polynomial in x at a given value of x can be formulated as an accumulation. We evaluate the polynomial

a_nxⁿ + a_n-1x^n-1 + … + a₁x + a₀

using a well-known algorithm called Horner's rule, which structures the computation as

( … (a_nx + a_n-1)x + … + a₁)x + a₀

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₀. Fill in the following template to produce a procedure that evaluates a polynomial using Horner's rule. Assume 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))

For example, to compute 1 + 3x + 5x³ + x⁵ at x = 2 you would evaluate

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

Remembering that accumulate is effectively equivalent to starting with some initial value, then going through the supplied list backwards from the last item to the first, applying op to each item and the accumulated result so far, we're actually going to start at the n^th coefficient and work backwards towards the 0^th one. This allows use to define the recursive relationship here as: multiply the accumulated result so far by x and then add the next coefficient.

Let's put this into code:

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms)
                (+ this-coeff (* x higher-terms)))
              0
              coefficient-sequence))

And give it a test:

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