Ex. 2.87

Adding a test for zero is straightforward for polynomials. We simply check all the terms. If every term’s coefficient is =zero?, then the polynomial itself is considered to equal zero. My procedure checks the first element in the term list, and then term list consisting of the remaining terms. It will return true if the list is empty. That also means that polynomials with no terms will be =zero?, which is a reasonable way to deal with them.

Ex. 2.88

Since we already have a procedure for adding polynomials, and subtraction is just adding a negative, we can define subtraction by negating the subtrahend and adding that to the minuend. That means we need a way to negate a poynomial. Negation is done by multiplying by -1. My solution does this by creating a polynomial with a single constant term. Here is the procedure internal to the polynomial package that handles subtraction:

(define (sub-poly p1 p2)
  (if (same-variable? (variable p1) (variable p2))
      (add-poly p1
                (mul-poly p2
                          (make-poly (variable p2) '((0 -1)))
                          )
                )
      (error "Polys not in same var -- SUB-POLY"
             (list p1 p2)
             )
      )
  )

The hint given guides the approach taken here, although it suggests defining negation as a generic operation. That is probably a better approach from the point of view of abstraction, but it also suggests an approach that negates term-by-term, requiring another routine to be written.

Using multiplication by a constant allows us to write a shorter function (in code) that relies on operations that are already known to work. It does require us to create a polynomial on-the-fly for our constant. Note that the polynomial generated is not built in the generic system, but with the make-poly constructor internal to the polynomial package. The reason we cannot use a generic value there is that arguments to our internal procedures are not generic values (at least not of the polynomial type), since apply-generic strips the type tag.

This approach does make subtraction of polynomials require more computation than addition. If time performance becomes a concern this would likely be a routine worth optimizing by avoiding the multiplication step.

Ex. 2.89

Dense polynomials aren’t all that different from the sparse polynomials in terms of construction and access routines. So for the most part, those procedures are unchanged. A significant difference is that the accessors for individual terms (order and coeff) cannot be used directly, as there are no individual terms as such. Getting this information may still be useful, however, so similar routines are defined using term lists as arguments instead of a single term.

When implementing the arithmetic routines for dense polynomials, we find that the list approach allows for some simplification. When lists are of the same length, we can use map to run the operation on the whole list to produce a complete term list. Thus in many cases, the only thing we need is term lists of the same length. To do this, there is a routine called add-leading-zeros that pads out whichever list is shorter. Multiplication requires a bit more work, but a similar padding approach is used, based on traditional manual arithmetic methods: one term is multiplied by all the terms and the result is shifted by adding trailing zeros; in the end, the partial products are added up.

Ex. 2.90

The changes required to implement both types in the same system are not difficult to figure out, but there a lot of things that need to be slightly modified. Each distinct sub-type may need a new name and a corresponding update in the function table. Renaming is indeed the only change required for the sparse type, and the dense type does not even require that. The new polynomial package then has no operations implemented in it; it simply relies on the underlying types, in similar fashion to the complex type. The only thing that is needed, then, is some way to have the subtypes work seamlessly with each other.

My approach is to make use of the type hierarchy, and just coerce one type to the other. In the dense package, I added a raise operation that will make it a sparse poly. I have not written a corresponding drop operation, which means that mixed operations will always end up as sparse polynomials. This is something of a judgement call; my reasoning is that sparse polynomials are unlikely to benefit from conversion to dense ones, and arithmetic operations are unlikely to change that. An argument could be made to choose a particular order at which denseness is preferred, but that would also add extra computation time for every sparse polynomial operation. Making use of the type hierarchy means that we can perform mixed operations and compare polynomials with hardly any extra code.

Ex. 2.91

Here’s the relevant portion of the solution that computes the division result:

 (let ((rest-of-result
        (div-terms (term-list (sub-poly (make-poly var L1)
                                        (make-poly var (mul-terms L2
                                                                  (list (make-term new-o new-c)))
                                                   )
                                        )
                              )
                   L2
                   var
                   )
        )
       )
   (list (cons (make-term new-o new-c) (quotient rest-of-result))
         (remainder rest-of-result)
         )
   )

We can see that rest-of-result is created by recursively calling div-terms. This follows the standard algorithm for division, in which the ‘new’ term, which will be part of the quotient, is multiplied by the divisor (L2) and subtracted from the current dividend. Note that a term-list is created from the new term on-the-fly. The polynomial that is the result of the multiplication is subtracted from the current dividend (L1), it will produce a new dividend with the leading term eliminated. The division recurses with this smaller polynomial, until div-terms returns only a remainder.

The complete result is built using the quotient and remainder from rest-of-result. In the last step, we must add the new term at the head of the quotient of the lower terms. The remainder is passed up unchanged, as it is already complete.

Note that although this division is only defined for sparse polynomials, the use of raise means that dense polynomials can be divided as well (although the result will always be a sparse polynomial). That does highlight one issue that arises from raising without including a drop — even when working with dense polynomials only, you may get a sparse result.

Ex. 2.92

This one is a complex and extensive change. It is a skipped problem for this chapter. As a rough outline of what I’d do, each sparse term would be changed to add a list of variables and their order, with the coefficient being separate. Arithmetic would need to look at all variables, and re-order the results as necessary. Multiplication would still add partial products in the same way it does now, so it’s not any more difficult. Both would need a way to figure out which terms can actually be combined, which is where the ordering comes in.

Doing division would be particularly tricky; that’s why it isn’t included in the exercise. I don’t have a good grasp on how it would work, but it seems that finding the Gröbner Basis might be required (or at least it’d be the best method).

Another approach to the problem, analogous to the dense polynomials, could be done using multidimensional arrays. Each variable would be stored using an additional dimension. Thus the term 12x⁵y²z would be stored as a 12 at index [5,2,1]. This could be done without necessarily imposing an order — each polynomial could have a custom mapping to its array, and operations would typically lead to a re-mapping of the variables. This system might be computationally more expensive, but it’s conceptually simpler.

The extended exercise with rational polynomials will be covered, but owing to the length of that problem it will be a separate post.

Solutions 2.5.3