SICP 全笔记

Exercise 2.95. Define P1, P2, and P3 to be the polynomials

$$ P_1: x^2 - 2x + 1 P_2: 11x^2 + 7 P_3: 13x + 5 $$ Now define Q1 to be the product of P1 and P2 and Q2 to be the product of P1 and P3, and use greatest-common-divisor (exercise 2.94) to compute the GCD of Q1 and Q2. Note that the answer is not the same as P1. This example introduces noninteger operations into the computation, causing difficulties with the GCD algorithm.61 To understand what is happening, try tracing gcd-terms while computing the GCD or try performing the division by hand.

整个过程如下：

(load "94-gcd-poly.scm")

(define p1 (make-polynomial 'x '((2 1) (1 -2) (0 1))))
(define p2 (make-polynomial 'x '((2 11) (0 7))))
(define p3 (make-polynomial 'x '((1 13) (0 5))))

(define q1 (mul p1 p2))

(define q2 (mul p1 p3))

(greatest-common-divisor q1 q2)

;Value 18: (polynomial x (2 1458/169) (1 -2916/169) (0 1458/169))

最终的结果并不是 p1，我们使用 (trace gcd-terms) 来跟踪 gcd-terms 的执行情况：

[Entering #[compound-procedure 23 gcd-terms]
    Args: ((4 11) (3 -22) (2 18) (1 -14) (0 7))
          ((3 13) (2 -21) (1 3) (0 5))]
in remainder-terms:((4 11) (3 -22) (2 18) (1 -14) (0 7)) & ((3 13) (2 -21) (1 3) (0 5))
result:(((1 11/13) (0 -55/169)) ((2 1458/169) (1 -2916/169) (0 1458/169)))
[Entering #[compound-procedure 23 gcd-terms]
    Args: ((3 13) (2 -21) (1 3) (0 5))
          ((2 1458/169) (1 -2916/169) (0 1458/169))]
in remainder-terms:((3 13) (2 -21) (1 3) (0 5)) & ((2 1458/169) (1 -2916/169) (0 1458/169))
result:(((1 2197/1458) (0 845/1458)) ())
[Entering #[compound-procedure 23 gcd-terms]
    Args: ((2 1458/169) (1 -2916/169) (0 1458/169))
          ()]
[((2 1458/169) (1 -2916/169) (0 1458/169))
      <== #[compound-procedure 23 gcd-terms]
    Args: ((2 1458/169) (1 -2916/169) (0 1458/169))
          ()]
[((2 1458/169) (1 -2916/169) (0 1458/169))
      <== #[compound-procedure 23 gcd-terms]
    Args: ((3 13) (2 -21) (1 3) (0 5))
          ((2 1458/169) (1 -2916/169) (0 1458/169))]
[((2 1458/169) (1 -2916/169) (0 1458/169))
      <== #[compound-procedure 23 gcd-terms]
    Args: ((4 11) (3 -22) (2 18) (1 -14) (0 7))
          ((3 13) (2 -21) (1 3) (0 5))]

上面的跟踪还包括了在 remainder-terms 过程中打印的信息。看到这个信息之后我们更加明白，导致最终结果为分数的原因是我们的多项式相除的算法：$11x^4$ 与 $13x^3$ 在第一次相除的时候商就已经产生 11/13 这样的分数了。