SICP Exercise 2.34

Question

Evaluating a polynomial in x at a given value of x can be formulated as an accumulation. We evaluate the polynomial anxn+an1xn1++a1x+a0

using a well-known algorithm called Horner’s rule, which structures the computation as ((anx+an1)x++a1)x+a0

In other words, we start with an, multiply by x, add an1, multiply by x, and so on until we reach a0.

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 sequence, from a0 to an.

(define
  (horner-eval x coefficient-sequence)
  (accumulate
   (λ (this-coeff higher-terms)
     ??)
   0
   coefficient-sequence))

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

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

Answer

The question basically tells you exactly how op should be constructed. Since op evaluates the list in reverse order, we can simply start with this-coeff and add to it all the higher terms multiplied by x.

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

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

Results:

79