## **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

## 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