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_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0$$

using a well-known algorithm called Horner’s rule, which structures the computation as $$(\dots (a_{n}x+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$.

copy(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

copy(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.

copy(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:

copy79