Exercise 2.94

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)
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s