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))
           ((3 (- -22 -231/13))
            (2 (- 18 33/13))
            (1 (- -14 55/13))
            (0 7)))

(gcd-terms ((3 13) (2 -21) (1 3) (0 5))
           ((3 -55/13) (2 201/13) (1 -237/13) (0 7)))

(gcd-terms ((3 -55/13) (2 201/13) (1 -237/13) (0 7))
           ((2 (- -21 (* 201/13 (* -13/55 13))))
            (1 (- 3 (* -237/13 (* -13/55 13))))
            (0 (- 5 (* 7 (* -13/55 13))))))

(gcd-terms ((3 -55/13) (2 201/13) (1 -237/13) (0 7))
           ((2 1458/55) (1 -2916/55) (0 1458/55)))

(gcd-terms ((2 1458/55) (1 -2916/55) (0 1458/55))
           ((2 (- 201/13 (* -2916/55 (* 55/1458 -55/13))))
            (1 (- -237/13 (* 1458/55 (* 55/1458 -55/13))))
            (0 7)))

(gcd-terms ((2 1458/55) (1 -2916/55) (0 1458/55))
           ((2 7) (1 -14) (0 7)))

(gcd-terms ((2 7) (1 -14) (0 7))
           ((1 (- -2916/55 (* -14 (* 1/7 1458/55))))
            (0 (- 1458/55 (* 7 (* 1/7 1458/55))))))

(gcd-terms ((2 7) (1 -14) (0 7))
           ((1 0) (0 0)))

(gcd-terms ((2 7) (1 -14) (0 7))
           ())

((2 7) (1 -14) (0 7))

(polynomial (x (2 7) (1 -14) (0 7)))