<< Previous exercise (2.90) | Index | Next exercise (2.92) >>
(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 (div-terms (sub-terms L1 (mul-term-by-all-terms (make-term new-o new-c) L2)) L2))) (list (adjoin-term (make-term new-o new-c) (first rest-of-result)) (second rest-of-result)))))))) (define (div-poly p1 p2) (if (same-variable? (variable p1) (variable p2)) (map (lambda (termlist) (make-poly (variable p1) termlist)) (div-terms (term-list p1) (term-list p2))) (error "Polys not in same var -- DIV-POLY" (list p1 p2))))
(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))) (new-t (make-term new-o new-c))) (let ((rest-of-result (div-terms (add-poly L1 (negate (mul-poly (list new-t) L2))) L2))) (list (adjoin-term new-t (car rest-of-result)) (cadr rest-of-result)))))))) (define (div-poly poly1 poly2) (if (same-variable? (variable poly1) (variable poly2)) (make-poly (variable poly1) (div-terms (term-list poly1) (term-list poly2))) (error "not the same variable" (list poly1 poly2))))
The answer above has one inaccurate point: add-terms & mul-terms should be used instead of add-poly & mul-poly in the first paragraph.
(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
(div-terms (sub-terms L1
(mul-terms L2
(list (make-term new-o new-c))))
L2)))
(list (adjoin-term (make-term new-o new-c)
(car rest-of-result))
(cadr rest-of-result))))))))
Here's an answer that modifies the given code a bit to be easier to work with, and makes use of the mul-term-by-all-terms procedure. Also a corrected div-poly procedure, since the one in the first post is analogous to add-poly, when it shouldn't be since div-terms returns a list as should div-poly.
(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 ((first-term (make-term (- (order t1) (order t2)) (div (coeff t1) (coeff t2))))) (let ((rest-of-result (div-terms (sub-terms l1 (mul-term-by-all-terms first-term l2)) l2))) (list (adjoin-term first-term (car rest-of-result)) (cadr rest-of-result)))))))) (define (div-poly p1 p2) (if (same-variable? (variable p1) (variable p2)) (let ((results (div-terms (term-list p1) (term-list p2)))) (list (make-poly (variable p1) (car results)) (cadr results))) (error "Polys not in same var -- div-poly" (list p1 p2))))
All the solutions above missed the point that the results of div-poly are two polynomials. What they returns are a quotient poly and a remainder term list. When we return the result, we should make two polynomials, not one. The correct implementation for div-poly should be:
(define (div-poly p1 p2)
(if (same-variable? (variable p1) (variable p2))
(let ((result (div-terms (term-list p1)
(term-list p2))))
(list (make-poly (variable p1)
(car result))
(make-poly (variable p1)
(cadr result))))
(error "Variable is not the same -- DIV-POLY" (list (variable p1) (variable p2)))))
My div-terms is similar to the one of Gera but I use the fact that the first term of L1 is canceled by the new term multiplied by the first term of L2 so we don't have to touch the first term of L1 and L2 when we do the subtraction. Doing this we can save one multiplication of two terms. Here is the little improvement:
(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
(div-terms (sub-terms (rest-terms L1) ; only the rest terms of L1
(mul-term-by-all-terms
(make-term new-o new-c)
(rest-terms L2))) ; only the rest terms of L2
L2)))
(list (adjoin-term (make-term new-o new-c) (car rest-of-result))
(cadr rest-of-result))))))))
woofy