Exercise 2.34 of SICP

Exercise 2.34: Evaluating a polynomial in x at a given value of x can be formulated as an accumulation. We evaluate the polynomial
p(x) = 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
(\cdots (a_n x + a_{n-1})x + \cdots + a_1)x + a_0
In other words, we start with an, multiply by x, add an-1, multiply by x, and so on, until we reach a0. 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 a0 through an.

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

I included a non-abstracted version of Horner’s method for clarity.

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

Leave a Reply