SICP 読み (94) 2.5.3 例: 記号代数
問題処理 (懐
単体試験の方で確認してみると、gcd-terms で符号が逆転しているのを昨晩確認済み。
以下のような試験を書いて
("2.97's gcd-terms"
(let ((L1 '((5 1) (3 -1) (2 -1) (0 1)))
(L2 '((4 1) (3 1) (2 1) (1 -2) (0 -1))))
(assert-equal '((1 1) (0 -1))
(gcd-terms L1 L2))
(assert-equal '((1 1) (0 -1))
(gcd-terms L2 L1)))
)確認してみると
$ test/run-test.scm -vv - (test suite) 2.5.3 -- (test case) gcd-terms: .F expected:<((1 1) (0 -1))> but was:<((1 -1) (0 1))> in 2.97's gcd-terms F expected:<((1 1) (0 -1))> but was:<((1 -1) (0 1))> in 2.97's gcd-terms -- (test case) first-term: . -- (test case) max-order: . -- (test case) int-fct is 1?: . -- (test case) mul-term-by-all-terms: . -- (test case) div-terms: . -- (test case) result's GCD: . -- (test case) result: . -- (test case) retuce-terms: . 10 tests, 17 assertions, 15 successes, 2 failures, 0 errors Testing time: 0.035490999999999995 $
との事。
gcd-terms を見てると
(define (gcd-terms L1 L2)
(define (gcd-terms-iter L1 L2)
(if (empty-termlist? L2)
L1
(gcd-terms L2 (pseudoremainder-terms L1 L2))))
(div-by-gcd (gcd-terms-iter L1 L2)))ってなっていたのを発見したんですが、修正しても変化ナシ。
(define (gcd-terms L1 L2)
(define (gcd-terms-iter L1 L2)
(if (empty-termlist? L2)
L1
(gcd-terms-iter L2 (pseudoremainder-terms L1 L2))))
(div-by-gcd (gcd-terms-iter L1 L2)))再帰呼び出しで gcd-terms-iter を呼ばずに gcd-terms (外のガワ) を呼び出していた。ただ、修正して試験しても挙動は変わらず。何故にこうなるか、が全然把握できてない (ため息
置き換え勝負なリキは無いなぁ ...
とは言えやってみないとワケワカなんで頑張れ自分。
(gcd-terms '((5 1) (3 -1) (2 -1) (0 1)) '((4 1) (3 1) (2 1) (1 -2) (0 -1)))
(div-by-gcd (gcd-terms-iter '((5 1) (3 -1) (2 -1) (0 1))
'((4 1) (3 1) (2 1) (1 -2) (0 -1))))
(div-by-gcd (gcd-terms-iter
'((4 1) (3 1) (2 1) (1 -2) (0 -1))
(pseudoremainder-terms '((5 1) (3 -1) (2 -1) (0 1))
'((4 1) (3 1) (2 1) (1 -2) (0 -1)))))pseudoremainder-terms ん中
(cadr (div-terms
(mul-term-by-all-terms
(make-term
0
(expt (coeff (first-term
'((4 1) (3 1) (2 1) (1 -2) (0 -1))))
(+ 1 (- (order
(first-term
'((5 1) (3 -1) (2 -1) (0 1))))
(order
(first-term
'((4 1) (3 1) (2 1) (1 -2) (0 -1))))))))
'((5 1) (3 -1) (2 -1) (0 1)))
'((4 1) (3 1) (2 1) (1 -2) (0 -1))))
(cadr (div-terms
(mul-term-by-all-terms '(0 (expt (coeff '(4 1))
(+ 1 (- (order '(5 1))
(order '(4 1))))))
'((5 1) (3 -1) (2 -1) (0 1)))
'((4 1) (3 1) (2 1) (1 -2) (0 -1))))
(cadr (div-terms
(mul-term-by-all-terms '(0 1)
'((5 1) (3 -1) (2 -1) (0 1)))
'((4 1) (3 1) (2 1) (1 -2) (0 -1))))
(cadr (div-terms '((5 1) (3 -1) (2 -1) (0 1))
'((4 1) (3 1) (2 1) (1 -2) (0 -1))))
(cadr '(((1 1) (0 -1)) ((3 -1) (2 2) (1 -1))))
'((3 -1) (2 2) (1 -1))むむ。続きを。(cadr と car を間違えてました)
(div-by-gcd (gcd-terms-iter
'((4 1) (3 1) (2 1) (1 -2) (0 -1))
(pseudoremainder-terms '((5 1) (3 -1) (2 -1) (0 1))
'((4 1) (3 1) (2 1) (1 -2) (0 -1)))))
(div-by-gcd (gcd-terms-iter
'((4 1) (3 1) (2 1) (1 -2) (0 -1))
'((3 -1) (2 2) (1 -1))))
(div-by-gcd (gcd-terms-iter
'((3 -1) (2 2) (1 -1))
(pseudoremainder-terms '((4 1) (3 1) (2 1) (1 -2) (0 -1))
'((3 -1) (2 2) (1 -1)))))で又 pseudoremainder-terms の中
(pseudoremainder-terms '((4 1) (3 1) (2 1) (1 -2) (0 -1))
'((3 -1) (2 2) (1 -1)))
(cadr (div-terms
(mul-term-by-all-terms
(make-term
0
(expt (coeff (first-term
'((3 -1) (2 2) (1 -1))))
(+ 1 (- (order
(first-term
'((4 1) (3 1) (2 1) (1 -2) (0 -1))))
(order
(first-term
((3 -1) (2 2) (1 -1))))))))
'((4 1) (3 1) (2 1) (1 -2) (0 -1)))
'((3 -1) (2 2) (1 -1))))
(cadr (div-terms
(mul-term-by-all-terms (make-term 0 (expt -1 2))
'((4 1) (3 1) (2 1) (1 -2) (0 -1)))
'((3 -1) (2 2) (1 -1))))
(cadr (div-terms
(mul-term-by-all-terms (make-term 0 1)
'((4 1) (3 1) (2 1) (1 -2) (0 -1)))
'((3 -1) (2 2) (1 -1))))
(cadr (div-terms '((4 1) (3 1) (2 1) (1 -2) (0 -1)) '((3 -1) (2 2) (1 -1))))
(cadr '(((1 -1) (0 -3)) ((2 6) (1 -5) (0 -1))))
'((2 6) (1 -5) (0 -1))再度戻る
(div-by-gcd (gcd-terms-iter
'((3 -1) (2 2) (1 -1))
(pseudoremainder-terms '((4 1) (3 1) (2 1) (1 -2) (0 -1))
'((3 -1) (2 2) (1 -1)))))
(div-by-gcd (gcd-terms-iter
'((3 -1) (2 2) (1 -1))
'((2 6) (1 -5) (0 -1))))
(div-by-gcd (gcd-terms-iter
'((2 6) (1 -5) (0 -1))
(psedoremainder-terms '((3 -1) (2 2) (1 -1))
'((2 6) (1 -5) (0 -1)))))再び psedoremainder-terms
(psedoremainder-terms '((3 -1) (2 2) (1 -1))
'((2 6) (1 -5) (0 -1)))
(cadr (div-terms
(mul-term-by-all-terms (make-term
0
(expt (coeff (first-term
'((2 6) (1 -5) (0 -1))))
(+ 1 (- (order
(first-term
'((3 -1) (2 2) (1 -1))))
(order
(first-term
'((2 6) (1 -5) (0 -1))))))))
'((3 -1) (2 2) (1 -1)))
'((2 6) (1 -5) (0 -1))))
(cadr (div-terms
(mul-term-by-all-terms (make-term 0 (expt 6 2))
'((3 -1) (2 2) (1 -1)))
'((2 6) (1 -5) (0 -1))))
(cadr (div-terms '((3 -36) (2 72) (1 -36)) '((2 6) (1 -5) (0 -1))))
(cadr '(((1 -6) (0 7)) ((1 -7) (0 7))))
'((1 -7) (0 7))そして戻る
(div-by-gcd (gcd-terms-iter
'((2 6) (1 -5) (0 -1))
(psedoremainder-terms '((3 -1) (2 2) (1 -1))
'((2 6) (1 -5) (0 -1)))))
(div-by-gcd (gcd-terms-iter '((2 6) (1 -5) (0 -1)) '((1 -7) (0 7))))
(div-by-gcd (gcd-terms-iter
'((1 -7) (0 7))
(psedoremainder-terms '((2 6) (1 -5) (0 -1)) '((1 -7) (0 7)))))だんだんリストが短くなってきたんですが、これでは原因の特定が (以下略
(psedoremainder-terms '((2 6) (1 -5) (0 -1)) '((1 -7) (0 7)))
(cadr (div-terms
(mul-term-by-all-terms (make-term
0
(expt (coeff (first-term
'((1 -7) (0 7))))
(+ 1 (- (order
(first-term
'((2 6) (1 -5) (0 -1))))
(order
(first-term
'((1 -7) (0 7))))))))
'((2 6) (1 -5) (0 -1)))
'((1 -7) (0 7))))
(cadr (div-terms
(mul-term-by-all-terms (make-term 0 (expt -7 2))
'((2 6) (1 -5) (0 -1)))
'((1 -7) (0 7))))
(cadr (div-terms '((2 294) (1 -245) (0 -49)) '((1 -7) (0 7))))
(cadr '(((1 -42) (0 -7)) ()))
'()やた。'() が戻るぞ。どうなるんだ。
(div-by-gcd (gcd-terms-iter
'((1 -7) (0 7))
(psedoremainder-terms '((2 6) (1 -5) (0 -1)) '((1 -7) (0 7)))))
(div-by-gcd (gcd-terms-iter
'((1 -7) (0 7)) '()))
(div-by-gcd '((1 -7) (0 7)))
'((1 -1) (0 1))うーん。見事に符号逆転。div-terms が悪いのかなぁ。ここでは置き換えせずに gosh でいきなり答えを出してますので、div-terms を上から順に置き換えてみる。まずは最初のソレから。ちなみに実装によれば商が ((1 1) (0 -1)) で余りが ((3 -1) (2 2) (1 -1)) になっています。
(div-terms '((5 1) (3 -1) (2 -1) (0 1)) '((4 1) (3 1) (2 1) (1 -2) (0 -1))) ;; t1 は '(5 1) ;; t2 は '(4 1) ;; (> (order t2) (order t1)) は #f ;; new-o は 1 new-c は 1 ;; L2 に (1 1) を掛けると ;; '((5 1) (4 1) (3 1) (2 -2) (1 -1)) ;; neg して '((5 -1) (4 -1) (3 -1) (2 2) (1 1)) ;; L1 に add (add-terms '((5 -1) (4 -1) (3 -1) (2 2) (1 1)) '((5 1) (3 -1) (2 -1) (0 1))) ;; 結果は ((4 -1) (3 -2) (2 1) (1 1) (0 1)) ;; これを L2 で割る (div-terms '((4 -1) (3 -2) (2 1) (1 1) (0 1)) '((4 1) (3 1) (2 1) (1 -2) (0 -1))) ;; t1 は '(4 -1) ;; t2 は '(4 1) ;; (> (order t2) (order t1)) は #f ;; new-o は 0 new-c は -1 ;; L2 に (0 -1) を掛けると ;; ((4 -1) (3 -1) (2 -1) (1 2) (0 1)) ;; neg して(とほほ)元に戻ります ;; L1 に add (add-terms '((4 -1) (3 -2) (2 1) (1 1) (0 1)) '((4 1) (3 1) (2 1) (1 -2) (0 -1))) ;; 結果は ((3 -1) (2 2) (1 -1) (0 0)) ;; これを L2 で割る (div-terms '((3 -1) (2 2) (1 -1) (0 0)) '((4 1) (3 1) (2 1) (1 -2) (0 -1))) ;; t1 は '(3 -1) ;; t2 は '(4 1) ;; (> (order t2) (order t1)) は #t ;; L1 を返却 '((3 -1) (2 2) (1 -1))
最終的に返却されるのは '(((1 1) (0 -1)) ((3 -1) (2 2) (1 -1))) になる。
うーん。大体コード見て置き換えてるからその通りになって当然なんだよね。gcd-terms で符号が逆になってる、という事は 2.96 の試験が足らないのか。
