SICP Exercise 2.96: Pseudo-Remainder Terms

1. Implement the procedure pseudoremainder-terms, which is just like remainder-terms except that it multiplies the dividend by the integerizing factor described above before calling div-terms. Modify gcd-terms to use pseudoremainder-terms, and verify that greatest-common-divisor now produces an answer with integer coefficients on the example in exercise 2.95.
2. The GCD now has integer coefficients, but they are larger than those of P₁. Modify gcd-terms so that it removes common factors from the coefficients of the answer by dividing all the coefficients by their (integer) greatest common divisor.

Part A: Introducing the Integerizing Factor

The calculation of the integerizing factor and the implementation of pseudoremainder-terms are described in the book as follows:

[…] if P and Q are polynomials, let O₁ be the order of P (i.e., the order of the largest term of P) and let O₂ be the order of Q. Let c be the leading coefficient of Q. Then it can be shown that, if we multiply P by the integerizing factor c^{1 + O₁ - O₂}, the resulting polynomial can be divided by Q by using the div-terms algorithm without introducing any fractions. The operation of multiplying the dividend by this constant and then dividing is sometimes called the pseudodivision of P by Q. The remainder of the division is called the pseudoremainder.

Note that, in order to calculated the integerizing factor, we need to be able to calculate exponents. Note also that, within our system, the c in c^{1 + O₁ - O₂} is a tagged type. This means that we'll need to add support for calculating exponentiation to our system. On the other hand, O₁ and O₂ are primitive integer values, so we'll need to convert the results of 1 + O₁ - O₂ to a tagged integer value so that it can be used as the exponent.

Let's begin with implementing support for exponentiation.

The book states that the modified GCD algorithm "really works only in the case of polynomials with integer coefficients". This means that our coefficient will always be an integer. As a result we can be pragmatic here and define the exponent operation for the integer package only. While defining it for the rational and real packages would be straightforward, this allows us to avoid having to define a generic logarithm operation in order to support complex numbers, as well as avoiding the complexities of calculating exponents for polynomial types.

We could define the integer implementation using the fast-expt implementation given in section 1.2.4 of the book. However, I chose simply to delegate the calculation to Scheme's built-in expt procedure:

(put 'exponent '(integer integer)
  (lambda (x y) (tag (expt x y))))

With that in place we can define a generic exponent operation in the usual manner:

(define (exponent b e)
  (apply-generic 'exponent b e))

We can now implement pseudoremainder-terms. This will still call through to div-terms and return the cadr of the results as before. However, we need to apply the integerizing factor to the first term-list and then apply div-terms to divide the resulting term-list by second term-list. As noted above, the result of the calculation 1 + O₁ - O₂ needs converted to a tagged integer type using make-integer in order that it can be used as the exponent when applying the generic exponent operation. In the implementation below we then convert this integerizing factor to a zero-order term in order that we can use our existing mul-term-by-all-terms procedure to apply the factor to the first term-list. Here's the code:

(define (pseudoremainder-terms L1 L2)
  (let* ((t1 (first-term L1))
         (t2 (first-term L2))
         (factor (exponent (coeff t2)
                           (make-integer (+ 1 (order t1) (- (order t2))))))
         (pseudoL1 (mul-term-by-all-terms (make-term 0 factor) L1)))
    (cadr (div-terms pseudoL1 L2))))

All that remains in part A is to modify gcd-terms to use pseudoremainder-terms instead of remainder-terms and we're done:

 (define (gcd-terms L1 L2)
  (if (empty-termlist? L2)
      L1
      (gcd-terms L2 (pseudoremainder-terms L1 L2))))

Let's see this in action. If you recall, in exercise 2.95 we defined two polynoials, q1 and q2, and calculating their GCD gave the following result:

> (greatest-common-divisor q1 q2)
(polynomial x dense-terms (rational (integer . 18954) integer . 2197)
                          (rational (integer . -37908) integer . 2197)
                          (rational (integer . 1458) integer . 169))

When we repeat this calculation with pseudoremainder-terms we now get the following result:

> (greatest-common-divisor q1 q2)
(polynomial x dense-terms (integer . 1458) (integer . -2916) (integer . 1458))

As you can see, just like in exercise 2.95, the coefficients hold the same relative ratios as the coefficients of P₁, i.e. 1:-2:1. However, the resulting polynomial now has (large) integer coefficients throughout.

Part B: Removing Common Factors

We now want to remove the common factors from the coefficients of the result of gcd-terms so that we simplify the calculated GCD as much as possible. If we assume we have a procedure, remove-common-factors, which does this then our gcd-terms implementation becomes:

(define (gcd-terms L1 L2)
  (if (empty-termlist? L2)
      (remove-common-factors L1)
      (gcd-terms L2 (pseudoremainder-terms L1 L2))))

So what does remove-common-factors need to do? Well firstly it will need to determine the highest common factor (a.k.a. the GCD) of all of the coefficients and then it will need produce a new term-list by dividing each of the coefficients in the term-list by this common factor.

In order to find the GCD of the coefficients, first observe that the GCD of any two coefficients must itself have the GCD of all of the coefficients as a factor. So in order to determine the GCD of all of the coefficients we can simply start with the first coefficient as our initial GCD candidate and then repeatedly find the GCD of our current candidate and the next coefficient until we've processed the entire term-list. Programmatically this can be expressed as:

(define (find-gcd c L)
  (if (empty-termlist? L)
      c
      (find-gcd (greatest-common-divisor c (coeff (first-term L)))
                (rest-terms L))))

Obviously we can't use this to find the GCD of an entirely empty term-list, as there will be no first term to start with. However, this is just a helper procedure to support the implementation of remove-common-factors. As an empty term-list with its common factors removed is just an empty term-list we won't even need to invoke find-gcd in such a case. This provides a basic skeleton for our implementation of remove-common-factors: we determine whether we're dealing with an empty term-list, returning an empty term-list if we are and actually performing the removal if we're not. Here's the skeleton:

(define (remove-common-factors L)
  (if (empty-termlist? L)
      L
      <RemoveCommonFactors>))

All that remains is to use find-gcd to determine the GCD of the coefficients and then divide all of the coefficients by this GCD. One way of achieving this division would be to write a procedure that iterates through the term-list, applying the division to each coefficient and building a new term-list with the results. However, we already have a method of dividing a term-list by another value: div-terms, so it makes sense to use that instead. Unfortunately div-terms requires a term-list as the divisor, and find-gcd produces a tagged integer value, not a term-list. This means we'll need to first convert our tagged integer value into a zero-order term-list. We can do this by creating an empty termlist (with the-empty-termlist), creating a zero-order term with the GCD of the coefficients as its coefficient, and then adding this term to the empty term-list (with adjoin-term). Note that the division is guaranteed to produce no remainder, so we can simply return the calculated quotient as the simplified GCD.

Here's the full implementation of remove-common-factors:

  (define (remove-common-factors L)
    (if (empty-termlist? L)
        L
        (let* ((gcd-coeff (find-gcd (coeff (first-term L)) (rest-terms L)))
               (divisor (adjoin-term (make-term 0 gcd-coeff) (the-empty-termlist))))
          (car (div-terms L divisor)))))

With that in place we can now retry our calculation of the GCD of q1 and q2 again:

> (greatest-common-divisor q1 q2)
(polynomial x dense-terms (integer . 1) (integer . -2) (integer . 1))

This time we get the expected result. We can now move on to the last exercise in the chapter, where we'll use gcd-poly to reduce rational functions to their simplest terms.