SICP Exercise 2.34
Question
Evaluating a polynomial in
using a well-known algorithm called Horner’s rule, which structures the
computation as
In other words, we start with
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
(define
(horner-eval x coefficient-sequence)
(accumulate
(λ (this-coeff higher-terms)
⟨??⟩)
0
coefficient-sequence))
For example, to compute
(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