Division of univariate polynomial
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
procedure on the model of
. The procedure checks to see if the two polys have the same variable. If so,
strips off the variable and passes the problem to
, which performs the division operation on term lists.
finally reattaches the variable to the result supplied by
. It is convenient to design
to compute both the quotient and the remainder of a division. Div-terms can take two term lists as arguments and return a list of the quotient term list and the remainder term list.
Complete the following definition of
by filling in the missing expressions. Use this to implement
, which takes two
as arguments and returns a list of the
(define (div-terms L1 L2) (if (empty-termlist? L1) (list (the-empty-termlist) (the-empty-termlist)) (let ((t1 (first-term L1)) (t2 (first-term L2))) (if (> (order t2) (order t1)) (list (the-empty-termlist) L1) (let ((new-c (div (coeff t1) (coeff t2))) (new-o (- (order t1) (order t2)))) (let ((rest-of-result <compute rest of result recursively> )) <form complete result> ))))))
There are no comments yet.
You must log in to post a comment.Login