Scheme - データによる抽象の構築(汎用演算のシステム(例: 記号代数(多項式の算術演算、項リストの表現、記号代数における型の階層構造(拡張問題: 有理関数(多項式の積と最大公約数(最大公約多項式, 整数化因子integerizing factor), 擬除算(pseudodivision), 擬剰余(pseudoremainder))))))

計算機プログラムの構造と解釈[第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.96-a, b.を解いてみる。

その他参考書籍

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

問題 2.96-a, b.

コード(BBEdit, Emacs)

sample.scm

(define (pseudoremainder-terms p1 p2)
  (let ((t1 (first-term p1))
        (t2 (first-term p2)))
    (let ((o1 (order t1))
          (o2 (order t2))
          (c2 (coeff t2)))
      (cadr (div-terms (mul (expt c2
                                  (+ 1
                                     (- o1 o2)))
                            p1)
                       p2)))))

(define (gcd-terms a b)
  (if (empty-termlist? b)
      a
      (gcd-terms (pseudoremainder-terms a b))))

手計算で確認。

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

(pseudoremainder-terms ((4 11) (3 -22) (2 18) (1 -14) (0 7))
                       ((3 13) (2 -21) (1 3) (0 5)))

;; t1;(4 11) t2:(3 13) o1:4 o2:3 c2:13 
(cadr
 (div-terms ((4 1859) (3 -3718) (2 3042) (1 -2366) (0 1183))
            ((3 13) (2 -21) (1 3) (0 5))))

(div-terms ((4 1859) (3 -3718) (2 3042) (1 -2366) (0 1183))
            ((3 13) (2 -21) (1 3) (0 5)))
;; 商の第一項
(1 143)
;; この結果に除数を掛ける
((4 1859) (3 -3003) (2 429) (1 715))
;; これを被除数から引く
((3 -715) (2 2613) (1 -3081) (0 1183))  ; (1)
;; この差を除数で割る
;; 商の第一項
(0 -55)
;; この結果に除数を掛ける
((3 -715) (2 1155) (1 -165) (0 -275))
;; これを被除数(1)から引く
((2 1458) (1 -2916) (0 1458))           ; (2)
;; この差を除数で割る
;; 除数の次数が被除数の次数を超えたので停止
;; よって剰余はこの被除数(2)

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

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

;;  t1:(3 13) t2:(2 1458) o1:3 o2:2 c2:1458
(cadr
 (div-terms ((3 27634932) (2 -44641044) (1 6377292) (0 10628820))
            ((2 1458) (1 -2916) (0 1458))))

(div-terms ((3 27634932) (2 -44641044) (1 6377292) (0 10628820))
           ((2 1458) (1 -2916) (0 1458)))

;; 商の第一項
(1 18954)
;; この結果に除数を掛ける
((3 27634932) (2 -55269864) (1 27634932))
;; これを被除数から引く
((2 10628820) (1 -21257640) (0 10628820))　 ;　(3)
;; この差を除数で割る
;; 商の第一項
(0 7290)
;; この結果に除数を掛ける
((2 10628820) (1 -21257640) (0 10628820))
;; これを被除数から引く
()
;; よって
(gcd-term Q1 Q2)
(polynomial (x ((2 1458) (1 -2916) (0 1458))))
;; 整数係数を持つ答えが生成出来た
;; b.
;; 全係数を整数の最大公約数で割ることで共通因子を除く
;; 全係数の整数の最大公約数は1458
(polynomial (x ((2 1) (1 -2) (0 1))))
;; これはP1と一致している