Exercise 2.34

in
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) <??>)
              0
              coefficient-sequence))

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]

Comments

At some time or another, most Blackberry users will wonder how to add an
icon to their homepage in order to quickly access
frequently used websites in just one click. Those who
dont will lose money  its that simple. The directory assistants urged the Florida animal
hospital to evaluate past data and call traffic from each of the phone
directory listings.

Check out my web blog - yellow pages scraper free new hidden object games

The autumn season promotion season is coming. You are welcome to buy an outboard engine to fit your boat. With a power Suzuki Marine on your boat you can go out to the deep sea for fishing.

Before you buy the Yamaha Outboard Motors , there are several points you need to consider with. You need to choose which type is better for your boat, the 4 stroke or the 2 stroke? A 4-stroke engine tends to be more sophisticated than a 2-stroke option as ignition process is split into several different cycles.

Start the boating season off right with proper outboard engine preparation. Ensuring that Yamaha Outboard Engines is in excellent working condition before leaving the driveway can prevent frustrating, embarrassing and costly delays at the boat launch. After storage, outboard engines need to be cleaned, inspected and tested before the first use of the season in http://www.suzukimarinesale.com/. Perform these checks in advance of any planned adventures.

The price is also the important factor for you when choose an outboard engine. Suzuki Outboard Motors can supply you factory price, discounts and free shipping cost. You are welcome to make an order today, we will supply you best service and fastest delivery.

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