SICP 読み (90) 2.5.3 例: 記号代数
ナチュラルな勘違いをしていました。reminder ぢゃなくて remainder ッス。The song remains the same だよ。(謎
guile のマニュアルとか見ても手続き定義されているようだけど何故だ、と
gosh> reminder *** ERROR: unbound variable: reminder Stack Trace: _______________________________________ 0 reminder 1 reminder gosh>
確認しつつ思っていた訳です。よく見りゃスペル違ってるし。
gosh> remainder #<subr remainder> gosh>
とほほほ。
で、一応 2.95 に着手する前に greatest-common-divisor を問題の要求通りに実装しておいて着手。
問題 2.95
これは実装云々ではなくて、トレイスな問題の模様。とりあえず試験を書いてみる。
("2-95"
(setup (lambda ()
(install-rational-package)
(install-scheme-number-package)
(install-polynomial-package)))
("not equall"
(let ((p1 (make-polynomial 'x '((2 1) (1 -2) (0 1))))
(p2 (make-polynomial 'x '((2 11) (0 7))))
(p3 (make-polynomial 'x '((1 13) (0 5)))))
(let ((q1 (mul p1 p2))
(q2 (mul p1 p3)))
(assert-not-equal p1 (greatest-common-divisor q1 q2))))
)
)パス。gosh で gcd-terms のトレイスがでれば楽なんですが多分無理。置き換えなソレをわしわし書いてくしか無いのか。一応、q1 と q2 の値も assert で確認できた方が良いな、ってかそこからやんなきゃ、なのか ...
ズルして gosh で確認。以下の assert を追加。
(assert-equal q1
'(polynomial x (4 11) (3 -22) (2 18) (1 -14) (0 7)))
(assert-equal q2
'(polynomial x (3 13) (2 -21) (1 3) (0 5)))メンドウなので gcd-terms んトコから置き換え開始。(reminder な typo はスルー)
(gcd-terms '((4 11) (3 -22) (2 18) (1 -14) (0 7))
'((3 13) (2 -21) (1 3) (0 5)))
(gcd-terms '((3 13) (2 -21) (1 3) (0 5))
(reminder-terms '((4 11) (3 -22) (2 18) (1 -14) (0 7))
'((3 13) (2 -21) (1 3) (0 5))))
(gcd-terms '((3 13) (2 -21) (1 3) (0 5))
(cadr (div-terms '((4 11) (3 -22) (2 18) (1 -14) (0 7))
'((3 13) (2 -21) (1 3) (0 5)))))ちょっとココで div-terms な再帰のみ (rest-of-result を作る処理) をトレイス。
(div-terms '((4 11) (3 -22) (2 18) (1 -14) (0 7))
'((3 13) (2 -21) (1 3) (0 5)))
;; new-o is 1 new-c is 0.8461538461538461 ??? <- 実数になったけど大丈夫??むー。実数になった時点で駄目っぽいのが予測できるんでやりたくないんだけどなぁ。(を
そのまま p.124 の下らへんに書いてある手法を使って div-terms をトレイスしてみる。
やる事は
- (make-term (L1 の次数 - L2 の次数) L2 の係数) する (整数化因子)
- L1 (被除数) に上の整数化因子を掛ける
- 上の結果を L2 で割る (div-terms の処理)
で机上トレイスしてたんですが、いつまで経っても終わる気配ナシ。
再度テキストを確認してみたら、整数化因子なソレがダウト。テキストによれば
(make-term 0 (expt L2の係数 (+ 1 (L1 の次数 - L2 の次数))))
が本当らしい。
これを元に机上で計算してみます。
(div-terms '((4 11) (3 -22) (2 18) (1 -14) (0 7)) '((3 13) (2 -21) (1 3) (0 5)))
です。
擬除算の準備
(mul-term-by-all-terms (make-term 0 (expt 13 (+ 1 (- 4 3)))) '((4 11) (3 -22) (2 18) (1 -14) (0 7))) ;; -> '((4 1859) (3 -3718) (2 3042) (1 -2366) (0 1183)) ;; この項リストを除算の処理において使用
除算の処理
;; '((4 1859) (3 -3718) (2 3042) (1 -2366) (0 1183)) と ;; '((3 13) (2 -21) (1 3) (0 5)) の除算 ;; まず、先頭の項の処理 ;; new-o は 1 で new-c は 143 (mul-term-by-all-terms '(1 143) '((3 13) (2 -21) (1 3) (0 5))) ;; -> '((4 1859) (3 -3003) (2 429) (1 715)) ;; neg すると '((4 -1859) (3 3003) (2 -429) (1 -715)) ;; L1 に加える (add-terms '((4 -1859) (3 3003) (2 -429) (1 -715)) '((4 1859) (3 -3718) (2 3042) (1 -2366) (0 1183))) ;; -> '((3 -715) (2 2613) (1 -3081) (0 1183)) (div-terms '((3 -715) (2 2613) (1 -3081) (0 1183)) '((3 13) (2 -21) (1 3) (0 5)))
繰り返す (もう一度)
;; 擬除算の準備 (mul-term-by-all-terms (make-term 0 (expt 13 (+ 1 (- 3 3)))) '((3 -715) (2 2613) (1 -3081) (0 1183))) ;; -> '((3 -9295) (2 33969) (1 -40053) (0 15379)) ;; この項リストを除算の処理で使用 ;; '((3 -9295) (2 33969) (1 -40053) (0 15379)) ;; '((3 13) (2 -21) (1 3) (0 5)) の除算 ;; 先頭の項の処理 ;; new-o は 0 で new-c は -715 (mul-term-by-all-terms '(0 -715) '((3 13) (2 -21) (1 3) (0 5))) ;; -> '((3 -9295) (2 15015) (1 -2145) (0 -3575)) ;; neg すると '((3 9295) (2 -15015) (1 2145) (0 3575)) ;; L1 に加える (add-terms '((3 9295) (2 -15015) (1 2145) (0 3575)) '((3 -9295) (2 33969) (1 -40053) (0 15379))) ;; -> '((2 18954) (1 -37908) (0 18954)) (div-terms '((2 18954) (1 -37908) (0 18954)) '((3 13) (2 -21) (1 3) (0 5)))
これで終わるハズなんですがもう少しトレイス。
繰り返す (多分これで一旦終わる)
;; 擬除算の準備 (mul-term-by-all-terms (make-term 0 (expt 13 (+ 1 (- 2 3)))) '((2 18954) (1 -37908) (0 18954))) ;; -> '((2 18954) (1 -37908) (0 18954)) ;; この項リストを除算の処理で使用 ;; '((2 18954) (1 -37908) (0 18954)) と ;; '((3 13) (2 -21) (1 3) (0 5)) の除算 ;; (list '() '((2 18954) (1 -37908) (0 18954))) が返却される
つづき
元に戻ってみる。
(gcd-terms '((3 13) (2 -21) (1 3) (0 5)) (cadr (div-terms '((4 11) (3 -22) (2 18) (1 -14) (0 7)) '((3 13) (2 -21) (1 3) (0 5))))) (gcd-terms '((3 13) (2 -21) (1 3) (0 5)) (cadr '(() ((2 18954) (1 -37908) (0 18954))))) (gcd-terms '((3 13) (2 -21) (1 3) (0 5)) '((2 18954) (1 -37908) (0 18954))) (gcd-terms '((2 18954) (1 -37908) (0 18954)) (reminder-terms '((3 13) (2 -21) (1 3) (0 5)) '((2 18954) (1 -37908) (0 18954)))) (gcd-terms '((2 18954) (1 -37908) (0 18954)) (cadr (div-terms '((3 13) (2 -21) (1 3) (0 5)) '((2 18954) (1 -37908) (0 18954)))))
うーん。再度 div-terms ですね。
(div-terms '((3 13) (2 -21) (1 3) (0 5)) '((2 18954) (1 -37908) (0 18954)))
もう一度
;; 擬除算の準備 (mul-term-by-all-terms (make-term 0 (expt 18954 (+ 1 (- 3 2)))) '((3 13) (2 -21) (1 3) (0 5))) ;; -> '((3 4670303508) (2 -7544336436) (1 1077762348) (0 1796270580)) ;; この項リストを除算の処理で使用 (とほほ ;; '((3 4670303508) (2 -7544336436) (1 1077762348) (0 1796270580)) と ;; '((2 18954) (1 -37908) (0 18954))) の除算 ;; 先頭の項の処理 ;; new-o は 1 で new-c は 246402 (mul-term-by-all-terms '(1 246402) '((2 18954) (1 -37908) (0 18954))) ;; -> '((3 4670303508) (2 -9340607016) (1 4670303508)) ;; neg すると '((3 -4670303508) (2 9340607016) (1 -4670303508)) ;; L1 に加える (add-terms '((3 -4670303508) (2 9340607016) (1 -4670303508)) '((3 4670303508) (2 -7544336436) (1 1077762348) (0 1796270580))) ;; -> '((2 1796270580) (1 -3592541160) (0 1796270580)) (div-terms '((2 1796270580) (1 -3592541160) (0 1796270580)) '((2 18954) (1 -37908) (0 18954)))
次で終わるか。(まだでした)
なんか目がちかちかする。
;; 擬除算の準備 (mul-term-by-all-terms (make-term 0 (expt 18954 (+ 1 (- 2 2)))) '((2 1796270580) (1 -3592541160) (0 1796270580))) ;; -> '((2 34046512573320) (1 -68093025146640) (0 34046512573320)) ;; この項リストを除算の処理で使用 (やれやれ ;; '((2 34046512573320) (1 -68093025146640) (0 34046512573320)) と ;; '((2 18954) (1 -37908) (0 18954))) を除算 ;; 先頭の項の処理 ;; new-o は 0 で new-c は 1796270580 (mul-term-by-all-terms '(0 1796270580) '((2 18954) (1 -37908) (0 18954))) ;; -> '((2 34046512573320) (1 -68093025146640) (0 34046512573320)) ;; neg すると '((2 -34046512573320) (1 68093025146640) (0 -34046512573320)) ;; L1 と加算 (add-terms '((2 -34046512573320) (1 68093025146640) (0 -34046512573320)) '((2 34046512573320) (1 -68093025146640) (0 34046512573320))) ;; -> '() (div-terms '() '((2 18954) (1 -37908) (0 18954)))
これ、どうなるんだろ。最初の条件分岐で
(list '() '())
が返却ですか。元に戻ってみると
(gcd-terms '((2 18954) (1 -37908) (0 18954)) (cadr (div-terms '((3 13) (2 -21) (1 3) (0 5)) '((2 18954) (1 -37908) (0 18954))))) (gcd-terms '((2 18954) (1 -37908) (0 18954)) (cadr '(() ()))) (gcd-terms '((2 18954) (1 -37908) (0 18954)) '())
これは '((2 18954) (1 -37908) (0 18954)) が返却されますな。おそらくはこれが戻される項リストのはずだな。
実装での動作確認は次の問題の範疇なんで今日はこれで終わり。
