SICP 2.5.3 Solutions
August 14, 2016 11:05
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, along with the term list consisting of the remaining terms. This definition also means that polynomials with no terms will be
=zero?, which is a reasonable way to deal with them.
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, and to make it easier to do this we create a polynomial with a single constant term. Here is the procedure that does the work, but note that is internal to the polynomial package:
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.
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. The only significant difference is that the accessors for individual terms (
coeff) cannot be used directly as there are no individual terms as such. Getting this information may still be useful, however, and 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 simpler methods. If we have lists of the same length, we can use
map to run the operation on the whole list to produce each term. Thus 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.
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.
Here’s the relevant portion of the solution that computes the division result:
We can see that
rest-of-result is created recursively, using the standard algorithm for division. The ‘new’ term, which will be part of the quotient, is multiplied by the divisor (L2). 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); that will produce a new dividend with the leading term eliminated. The procedure continues until the division cannot be performed, and the final dividend is the 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 to the head of the quotient. 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 get a sparse result.
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
12x^5^y^2^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.