SICP Exercise 2.88: Subtracting Polynomials

Extend the polynomial system to include subtraction of polynomials. (Hint: You may find it helpful to define a generic negation operation.)

The authors suggest that defining a generic negation operation may be useful in solving this exercise. Why would this be?

Well, if we consider what's required in order to subtract one polynomial from another then all will become clear. Assuming we have polynomials p1 and p2 and we want to calculate p1 - p2 then, similar to the addition of polynomials, we want to perform this term-wise:

• If there are terms of the same order in both p1 and p2 then we'll need a corresponding term in the resulting polynomial. The coefficient of this term will be the result of subtracting the coefficient of p2's term from the coefficient of p1's term.
• If only p1 has a term of a particular order then we need an identical term in the resulting polynomial, so we can just add it into the resulting polynomial directly.
• If only p2 has a term of a particular order then we need the negation of that term in the resulting polynomial.

So we could define an operation, sub-terms, that implements the steps above in a manner analogous to add-terms, and then define a procedure sub-poly which uses this in the same way as add-poly uses add-terms, using our generic negation operation to negate terms in p2 for which there is no corresponding term of the same order in p1.

Or we could be a bit smarter...

For any two values, a and b, that are of types representable in our system we know that a - b = a + (-b). In other words, subtracting b from a will give the same result as adding the negation of b to a.

When it comes to dealing with the terms of our polynomials this means that we can calculate the result of subtracting one term, t2, from another term, t1, by adding the result of negating t2 to t1. We can extend this to calculating the result of subtracting the polynomial p2 from p1 by negating all of the terms of p2, and then adding this new (negated) polynomial to p1. We already have an operation, add-poly, which will perform the addition. As a result, if we define a generic negation operation then implementing sub-poly simply becomes a case of evaluating add-poly with the first polynomial and the negation of the second polynomial.

So how do we define negation? Well, the generic operation itself is defined in the usual manner. We then just need to consider what to do for each of the different types:

• integer: Given an integer i we can calculate its negation by evaluating (- i), and then all we need to do is tag the results of this evaluation.
• rational: To negate a rational number we simply negate its numerator, which we can do in the same way as for integer, and then create a new rational number with the negated numerator and original denominator.
• real: A real number can be negated in the same way as for an integer.
• complex: To negate a complex number consider that, in order to calculate the negation of the complex number a + bi, we need to calculate -(a + bi). This is equivalent to (-a) + (-b)i. As a result we can calculate the negation by negating both the real and imaginary parts and constructing a new complex number from these negated components.
• polynomial: Finally, to negate a polynomial, we simply iterate through its terms and negate each one in turn using the generic negation operation. Once we've done this we create a new polynomial with the same indeterminate as the original and with the negated term list.

Okay, given that, here's the changes required to provide a generic negation operation:

(define (install-integer-package)
  …
  (put 'negate '(integer)
       (lambda (x) (tag (- x))))
  …
  'done)

(define (install-rational-package)
  ;; internal procedures
  …
  (define (negate-rat x)
    (make-rat (- (numer x)) (denom x)))
  …
  ;; interface to rest of the system
  …
  (put 'negate '(rational)
       (lambda (x) (tag (negate-rat x))))
  …
  'done)

(define (install-real-package)
  …
  (put 'negate '(real)
       (lambda (x) (tag (- x))))
  …
  'done)

(define (install-complex-package)
  …
  ;; internal procedures
  …
  (define (negate-complex z)
    (make-from-real-imag (negate (complex-real-part z))
                         (negate (complex-imag-part z))))
  …
  ;; interface to rest of the system
  …
  (put 'negate '(complex)
       (lambda (z) (tag (negate-complex z))))
  …
  'done)

(define (install-polynomial-package)
  ;; internal procedures
  …
  ;; Negation
  (define (negate-terms L)
    (if (empty-termlist? L)
        (the-empty-termlist)
        (let ((term (first-term L)))
          (adjoin-term (make-term (order term)
                                  (negate (coeff term)))
                       (negate-terms (rest-terms L))))))
  (define (negate-poly p)
    (make-poly (variable p)
               (negate-terms (term-list p))))
  …
  ;; interface to rest of the system
  …
  (put 'negate '(polynomial)
       (lambda (p) (tag (negate-poly p))))
  …
  'done)

Here's the negation in action:

> (negate (make-integer 42))
(integer . -42)
> (negate (make-rational 13 27))
(rational -13 . 27)
> (negate (make-real 3.14159))
(rational -3537115888337719 . 1125899906842624)
> (negate (make-complex-from-real-imag (make-real 3.5) (make-integer -32)))
(complex rectangular (rational -7 . 2) integer . 32)
> (define inner-poly (make-polynomial 
                      'y
                      (list (make-polynomial-term 2 (make-integer 1))
                            (make-polynomial-term 1 (make-rational -3 2))
                            (make-polynomial-term 0 (make-integer 42)))))
> (define outer-poly (make-polynomial
                      'x
                      (list (make-polynomial-term 4 (make-rational 7 2))
                            (make-polynomial-term 3 (make-complex-from-real-imag
                                                     (make-integer 42)
                                                     (make-integer -13)))
                            (make-polynomial-term 2 inner-poly)
                            (make-polynomial-term 0 (make-integer 5)))))
> (negate outer-poly)
(polynomial x (4 (rational -7 . 2))
              (3 (complex rectangular (integer . -42) integer . 13))
              (2 (polynomial y (2 (integer . -1))
                               (1 (rational 3 . 2))
                               (0 (integer . -42))))
              (0 (integer . -5)))

With that working, we just implement sub-poly as noted above:

(define (install-polynomial-package)
  …
  ;; Subtraction
  (define (sub-poly p1 p2)
    (add-poly p1 (negate-poly p2)))
  …
  ;; interface to rest of the system
  …
  (put 'sub '(polynomial polynomial)
       (lambda (p1 p2) (tag (sub-poly p1 p2))))
  …
  'done)

Now we can subtract one polynomial from another... Subtracting 5x⁴ + 4x³ + x + 1 from 4x⁴ + 2x² + 1 should give -x⁴ - 4x³ + 2x² - x:

> (sub (make-polynomial 'x
                        (list (make-polynomial-term 4 (make-integer 4))
                              (make-polynomial-term 2 (make-integer 2))
                              (make-polynomial-term 0 (make-integer 1))))
       (make-polynomial 'x
                        (list (make-polynomial-term 4 (make-integer 5))
                              (make-polynomial-term 3 (make-integer 4))
                              (make-polynomial-term 1 (make-integer 1))
                              (make-polynomial-term 0 (make-integer 1)))))
(polynomial x (4 (integer . -1))
              (3 (integer . -4))
              (2 (integer . 2))
              (1 (integer . -1)))

Looks good!