Source code.

From the top-down; first comes the generic operation.

(define (greatest-common-divisor x y) (apply-generic 'gcd x y))

Then the various implementations of `gcd`

– I think it only makes sense to define `gcd`

on polynomials and integers.

; in the integer package
(put 'gcd '(integer integer) (lambda (x y) (tag (gcd x y))))
; in the polynomial package
(define (gcd-poly p1 p2)
(if (same-variable? (variable p1) (variable p2))
(make-poly (variable p1)
(greatest-common-divisor (term-list p1)
(term-list p2)))
(error "Polys not in same var -- GCD-POLY"
(list p1 p2))))
...
...
...
(put 'gcd '(polynomial polynomial) (lambda (p1 p2) (tag (gcd-poly p1 p2))))

I still have two versions of term lists – dense and sparse and so `gcd-poly`

defers its operation to the relevant package – either the sparse or dense terms package – using the generic `greatest-common-divisor`

with term list arguments.

; in the dense terms package
(define (remainder-terms a b)
(cadr (div-terms a b)))
(define (gcd-terms a b)
(if (empty-termlist? b)
a
(gcd-terms b (remainder-terms a b))))
...
...
(put 'gcd '(dense dense) (lambda (t1 t2) (tag (gcd-terms t1 t2))))
(put 'gcd '(dense sparse) (lambda (t1 t2) (tag (gcd-terms t1 (sparse->dense t2)))))
; in the dense terms package
(define (remainder-terms a b)
(cadr (div-terms a b)))
...
...
; in the sparse-terms package
(define (gcd-terms a b)
(if (empty-termlist? b)
a
(gcd-terms b (remainder-terms a b))))
...
...
(put 'gcd '(sparse sparse (lambda (t1 t2) (tag (gcd-terms t1 t2))))
(put 'gcd '(sparse dense) (lambda (t1 t2) (tag (gcd-terms t1 (dense->sparse t2)))))

And finally; at this stage, I’m not interested in rigorously testing these exercises so once again I’ll just use the example given in the book.

(define (show x) (newline) (display x))
(define ps1 (make-sparse-polynomial 'x '((4 1) (3 -1) (2 -2) (1 2))))
(define ps2 (make-sparse-polynomial 'x '((3 1) (1 -1))))
(define pd1 (make-dense-polynomial 'x '(1 -1 -2 2 0)))
(define pd2 (make-dense-polynomial 'x '(1 0 -1 0)))
(show (greatest-common-divisor ps1 ps2))
(polynomial x sparse (2 -1) (1 1))
(show (greatest-common-divisor pd1 pd2))
(polynomial x dense -1 1 0)

### Like this:

Like Loading...

*Related*