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 \[a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0\]

using a well-known algorithm called Horner’s rule, which structures the computation as \[(\ldots (a_nx+a_{n-1})x+\cdots +a_1)x+a_0\]

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\).

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 \(a_0\) to \(a_n\).

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

For example, to compute \(1+3x+5x^3+x^5\) 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