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

$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

$\left(\cdots\left(a_nx + a_{n-1}\right)x + \cdots + a_1 \right) + 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 a sequence, from $a_0$ through $a_n$.

(define (horner-eval x coefficient-sequence)
(accumulate (lambda (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))

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