Scheme - データによる抽象の構築(汎用演算のシステム(例: 記号代数(多項式の算術演算、項リストの表現、記号代数における型の階層構造(拡張問題: 有理関数(多項式の積と最大公約数(最大公約多項式、手計算で求める))))))

計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルド エイブルソン (著) ジュリー サスマン (著)
ジェラルド・ジェイ サスマン (著)
Harold Abelson (原著) Julie Sussman (原著)
Gerald Jay Sussman (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の2(データによる抽象の構築)、2.5(汎用演算のシステム)、2.5.3(例: 記号代数)、多項式の算術演算、項リストの表現、記号代数における型の階層構造、拡張問題: 有理関数、問題 2.95.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 2.95.

手計算で確認。

P1: (polynomial (x (2 1) (1 -2) (0 1)))
P2: (polynomial (x (2 11) (0 7)))
P3: (polynomial (x (1 13) (0 5)))

Q1: (polynomial (x (add-terms ((4 11) (2 7))
                              (add-terms ((3 -22) (1 -14))
                                         (add-terms ((2 11) (0 7))
                                                    ())))))
Q1: (polynomial (x (add-terms ((4 11) (2 7))
                              (add-terms ((3 -22) (1 -14))
                                         ((2 11) (0 7))))))
Q1: (polynomial (x (add-terms ((4 11) (2 7))
                              ((3 -22) (2 11) (1 -14) (0 7)))))
Q1: (polynomial (x ((4 11) (3 -22) (2 18) (1 -14) (0 7))))

Q2: (polynomial (x (add-terms ((3 13) (2 5))
                              (add-terms ((2 -26) (1 -10))
                                         (add-terms ((1 13) (0 5))
                                                    ())))))
Q2: (polynomial (x (add-terms ((3 13) (2 5))
                              (add-terms ((2 -26) (1 -10))
                                         ((1 13) (0 5))))))
Q2: (polynomial (x (add-terms ((3 13) (2 5))
                              ((2 -26) (1 3) (0 5)))))
Q2: (polynomial (x ((3 13) (2 -21) (1 3) (0 5))))


Q1: (polynomial (x ((4 11) (3 -22) (2 18) (1 -14) (0 7))))
Q2: (polynomial (x ((3 13) (2 -21) (1 3) (0 5))))

(gcd-poly Q1 Q2)

(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))
           (remainder-terms ((4 11) (3 -22) (2 18) (1 -14) (0 7))
                            ((3 13) (2 -21) (1 3) (0 5))))

(remainder-terms ((4 11) (3 -22) (2 18) (1 -14) (0 7))
                 ((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 ((4 11) (3 -22) (2 18) (1 -14) (0 7))
           ((3 13) (2 -21) (1 3) (0 5)))

;; 商の第一項
(1 11/13)
;; この結果に除数を掛ける
((4 11) (3 -231/13) (2 33/13) (1 55/13))
;; これを被除数から引く
((3 -55/13) (2 201/13) (1 -237/13) (0 7))　 ; (1)
;; この差を除数で割る
;; 商の第一項
(0 -55/169)
;; この結果に除数を掛ける
((3 -55/13) (2 1155/169) (1 -165/169) (0 -275/169))
;; これを被除数(1)から引く
((2 1458/169) (1 -2916/169) (0 1458/169)) ; (2)
;; この差を除数で割る
;; 除数の次数が被除数の次数を超えたので停止
;; よって剰余はこの被除数(2)

(gcd-terms ((3 13) (2 -21) (1 3) (0 5))
           ((2 1458/169) (1 -2916/169) (0 1458/169)))

(gcd-terms ((2 1458/169) (1 -2916/169) (0 1458/169))
           (remainder-terms ((3 13) (2 -21) (1 3) (0 5))
                            ((2 1458/169) (1 -2916/169) (0 1458/169))))

(div-terms  ((3 13) (2 -21) (1 3) (0 5))
            ((2 1458/169) (1 -2916/169) (0 1458/169)))

;; 商の第一項
(1 2197/1458)
;; この結果に除数を掛ける
((3 13) (2 -26) (1 13))
;; これを被除数から引く
((2 5) (1 -10) (0 5))                   ; (3)
;; この差を除数で割る
;; 商の第一項
(0 845/1458)
;; この結果に除数を掛ける
((2 5) (1 -10) (0 5))
;; これを被除数から引く
()
;; よって最大公約数(最大公約多項式)は以下のようになる
(gcd-terms Q1 Q2)
(polynomial (x ((2 1458/169) (1 -2916/169) (0 1458/169))))