Chapter 2, Building Abstractions with Data

Section - 2.5 - Systems with Generic Operations

Exercise 2.94


Following are the required changes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
; gcd polynomial functions
(define (gcd-terms a b)
     (if (empty-termlist? b)
         a
         (gcd-terms b (remainder-terms a b))
     )
)

(define (remainder-terms a b)
      (cadr (div-terms a b))
)

(define (gcd-poly p1 p2)
    (if (same-variable? (variable p1) (variable p2))
        (make-poly (variable p1) (gcd-terms (term-list p1) (term-list p2)))
        (error "Polynomials are not in same variable")
    )
)


;changes for installing gcd

; generic gcd (outside all packages or global)
(define (greatest-common-divisor a b)
  (apply-generic 'greatest-common-divisor a b)
)

;in polynomial package
(put 'greatest-common-divisor '(polynomial polynomial) (lambda (a b) (tag (gcd-poly a b))))

; in integer package
(put 'greatest-common-divisor '(int int) (lambda (a b) (tag (gcd a b))))

; in 'scheme-number package
(put 'greatest-common-divisor '(scheme-number scheme-number) gcd)

Output:

1
2
3
4
> (define p1 (make-polynomial 'x (attach-tag 'sparse-termlist '((4 1) (3 -1) (2 -2) (1 2)))))
> (define p2 (make-polynomial 'x (attach-tag 'sparse-termlist '((3 1) (1 -1)))))
> (display (greatest-common-divisor p1 p2))
(polynomial x sparse-termlist (2 -1) (1 1))

Thus the gcd of $x^4 - x^3 - 2x^2 + 2x$ and $x^3 - x$ is $-x^2 + x$. Manually I got the same gcd but with opposite sign i.e. $x^2 - x$.

Note that I also found a bug in my old div-terms procedure where I should be using cadr but was using cdr instead.