Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 2.34

From Drewiki
Jump to: navigation, search

Problem

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

<math>a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0</math>

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

<math>\left(\cdots\left(a_nx + a_{n-1}\right)x + \cdots + a_1 \right) + a_0</math>

In other words, we start with <math>a_n</math>, multiply by x, add <math>a_{n-1}</math>, multiply by x, and so on, until we reach <math>a_0</math>. 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 <math>a_0</math> through <math>a_n</math>.

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

For example, to compute <math>1 + 3x + 5x^3 + x^5</math> at x = 2, you would evaluate

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

Solution

Here's the definition of accumulate from the text:

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

Here's a definition of horner-eval:

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

Test with the polynomial given in the problem formulation (the answer should be 79):

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

Output:

79

Personal tools