SICP

Exercise 2.91.    A univariate polynomial can be divided by another one to produce a polynomial quotient and a polynomial remainder. For example, Division can be performed via long division. That is, divide the highest-order term of the dividend by the highest-order term of the divisor. The result is the first term of the quotient. Next, multiply the result by the divisor, subtract that from the dividend, and produce the rest of the answer by recursively dividing the difference by the divisor. Stop when the order of the divisor exceeds the order of the dividend and declare the dividend to be the remainder. Also, if the dividend ever becomes zero, return zero as both quotient and remainder. We can design a  div-poly  procedure on the model of  add-poly  and  mul-poly . The procedure checks to see if the two polys have the same variable. If so,  div-poly  strips off the variable and passes the problem to  div-terms , which performs the division operation on term lists.  Div-poly

Exercise 2.90.   Suppose we want to have a polynomial system that is efficient for both sparse and dense polynomials. One way to do this is to allow both kinds of term-list representations in our system. The situation is analogous to the complex-number example of section  2.4 , where we allowed both rectangular and polar representations. To do this we must distinguish different types of term lists and make the operations on term lists generic. Redesign the polynomial system to implement this generalization. This is a major effort, not a local change. SOLUTION The code and tests are here .

Exercise 2.89.   Define procedures that implement the term-list representation described above as appropriate for dense polynomials. SOLUTION The code and tests are here . Procedure 'adjoin-term' Structure of term-list: [OrderOfPolynomial, (list of coefficients)] Maintaining the order of the polynomial as the first element allows us to avoid repeated  expensive 'length' calls on the coefficient list.  We assume that term lists are represented as lists of terms,  arranged from highest-order to lowest-order term. Procedures 'first-term' and 'first-term' Since we are using the term-list representation that is appropriate for  dense polynomials (see SICP text), we need to do some extra processing  to retrieve both the order and coefficient.

Exercise 2.88.    Extend the polynomial system to include subtraction of polynomials. (Hint: You may find it helpful to define a generic negation operation.) SOLUTION The code and tests are here .

Exercise 2.87.    Install   =zero?   for polynomials in the generic arithmetic package. This will allow   adjoin-term   to work for polynomials with coefficients that are themselves polynomials. SOLUTION The code and tests are here .