The Grinnell Scheme Web: Polynomials

Given any polynomial, multiplication, addition, and subtraction should be enough to write a procedure that takes integer values for the variables in the polynomial and computes the value of the polynomial, right?

Yes. For instance, if your polynomial is 2x^4 + 3x^3 - 12x^2 - 72x + 240, you could use a direct but sub-optimal construction that computes the value of each term of the polynomial separately and then adds them all up:

(define (poly-1 x)
  (+ (* 2 x x x x)
     (* 3 x x x)
     (* -12 x x)
     (* -72 x)
     240))

What do you mean ``sub-optimal''? Is there some other way to figure this value?

Well, you'll notice that in the definition above, the cube of x is figured first of all as part of the computation of the fourth power of x, and then in the next line it is figured all over again as part of the computation of 3x^3. Clearly there's some wasted effort here.

So, you'd try to save the intermediate results in local variables?

That would be one approach. A better idea is to use algebra to rearrange the expression into an algebraically equivalent form that can be evaluated more efficiently even if it less tractable as an expression.

Such as?

For the polynomial mentioned above, the form I have in mind is 240 +x(-72 + x(-12 + x(3 + 2x))), or, in Scheme,

(define (poly-2 x)
  (+ 240 (* x (+ -72 (* x (+ -12 (* x (+ 3 (* x 2)))))))))

It's harder to read, but it reduces the number of multiplications considerably.

That's a cute trick, with the alternating additions and multiplications. Will it work for any polynomial?

Yes. You just drop in each coefficient after a plus sign, in ascending order of the degree of the term it's attached to, and put an occurrence of the variable after each multiplication symbol. If your polynomial doesn't have a term of each degree, you can insert one with the coefficient zero, follow the method described above, and then simplify the resulting code. For instance, to compute 4x^3 - 6x + 5, write the body of your procedure as

(+ 5 (* x (+ -6 (* x (+ 0 (* x 4))))))

and then simplify it to

(+ 5 (* x (+ -6 (* x x 4))))

Next topic
Previous topic
Table of contents

This document is available on the World Wide Web as

http://www.math.grin.edu/~stone/scheme-web/polynomials.html

created June 30, 1995
last revised December 29, 1995