Exercise 2.34

Printer-friendly versionPrinter-friendly version

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

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

In other words, we start with an, multiply by x, add an-1, multiply by x, and so on, until we reach a0.[16] 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.

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

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

(horner-eval 2 (list 1 3 0 5 0 1))
[16] According to Knuth (1981), this rule was formulated by W. G. Horner early in the nineteenth century, but the method was actually used by Newton over a hundred years earlier. Horner’s rule evaluates the polynomial using fewer additions and multiplications than does the straightforward method of first computing an xn, then adding an-1xn-1, and so on. In fact, it is possible to prove that any algorithm for evaluating arbitrary polynomials must use at least as many additions and multiplications as does Horner’s rule, and thus Horner’s rule is an optimal algorithm for polynomial evaluation. This was proved (for the number of additions) by A. M. Ostrowski in a 1954 paper that essentially founded the modern study of optimal algorithms. The analogous statement for multiplications was proved by V. Y. Pan in 1966. The book by Borodin and Munro (1975) provides an overview of these and other results about optimal algorithms. [back]


Post new comment

  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <pre> <hr> <ul> <ol> <li> <dl> <dt> <dd> <img>
  • Lines and paragraphs break automatically.
  • Adds typographic refinements.

More information about formatting options