第5回SICP勉強会

1.3 高階手続きによる抽象

  • 手続きを扱う手続きを高階手続きという(higherorder procedures)

1.3.1 引数としての手続き

  • 引数に手続きをとることで抽象化できますよ、という話

問題1.25

;; 問題1.25

;; オリジナルのexpmod(p28)
;; baseのexp乗の、mの剰余を求める処理
(define (expmod base exp m)
  (define (square x)
    (* x x))
  (cond [(= exp 0) 1]
        [(even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m)]
        [else
         (remainder (* base (expmod base (- exp 1) m))
                    m)]))

;; fast-expr
;; bのn乗を求める処理
(define (fast-expt b n)
  (define (square x)
    (* x x))
  (cond [(= 0 n) 1]
        [(even? n) (square (fast-expt b (/ n 2)))]
        [else (* b (fast-expt b (- n 1)))]))

(fast-expt 2 10)
;; gosh> 1024


;; Alysa P. Hackerのexpmod
(define (expmod base exp m)
  (remainder (fast-expt base exp) m)) ;; suquareしてからremainder

(expmod 2 3 3)


;; 計算結果という意味では同一の結果が得られる。
;; オリジナルのexpmodは繰り返し毎にbaseの剰余を求めて、
;; 値があまり大きくならないようにしている。
;; Alyssaのexpmodでは一度に累乗を求めてからbaseの剰余を求めているので
;; remainderに時間がかかっている。

;; どこかがボトルネックになっているのか?
;; gosh> (fast-expt 10 10000)
;; gosh> (fast-expt 10 1000)
;; とすると、圧倒的に(fast-expt 10 10000)の方が遅い
;; またgosh> (fast-expt 100 10000)は体感的に(fast-expt 10 10000)と
;; ほぼ同じと考えられる
;; このことから高速テストにおいてボトルネックになるのは、除算ではなく ;; 大きな数の乗算の処理に時間がかかっていると推測できる

問題1.26

;; 問題1.26
(use slib)
(require 'trace)
(trace expmod)

;; Louiceのプログラム
(define (expmod base exp m)
  (cond [(= exp 0) 1]
        [(even? exp)
         (remainder (* (expmod base (/ exp 2) m)
                       (expmod base (/ exp 2) m))
                    m)]
        [else
         (remainder (* base (expmod base (- exp 1) m))
                    m)]))

;; gosh> (expmod 2 10 10)
;; CALL expmod 2 10 10
;;   CALL expmod 2 5 10
;;     CALL expmod 2 4 10
;;       CALL expmod 2 2 10
;;         CALL expmod 2 1 10
;;         RETN expmod 2
;;         CALL expmod 2 1 10
;;         RETN expmod 2
;;       RETN expmod 4
;;       CALL expmod 2 2 10
;;         CALL expmod 2 1 10
;;         RETN expmod 2
;;         CALL expmod 2 1 10
;;         RETN expmod 2
;;       RETN expmod 4
;;     RETN expmod 6
;;   RETN expmod 2
;;   CALL expmod 2 5 10
;;     CALL expmod 2 4 10
;;       CALL expmod 2 2 10
;;         CALL expmod 2 1 10
;;         RETN expmod 2
;;         CALL expmod 2 1 10
;;         RETN expmod 2
;;       RETN expmod 4
;;       CALL expmod 2 2 10
;;         CALL expmod 2 1 10
;;         RETN expmod 2
;;         CALL expmod 2 1 10
;;         RETN expmod 2
;;       RETN expmod 4
;;     RETN expmod 6
;;   RETN expmod 2
;; RETN expmod 4
;; 4

;; オリジナルのexpmod
(define (expmod base exp m)
  (define (square x)
    (* x x)) 
  (cond [(= exp 0) 1]
        [(even? exp)
         (remainder (square (expmod base (/ exp 2) m)) 
                    m)] 
        [else
         (remainder (* base (expmod base (- exp 1) m)) 
                    m)]))

;; gosh> (expmod 2 10 10)
;; CALL expmod 2 10 10
;;   CALL expmod 2 5 10
;;     CALL expmod 2 4 10
;;       CALL expmod 2 2 10
;;         CALL expmod 2 1 10
;;         RETN expmod 2
;;       RETN expmod 4
;;     RETN expmod 6
;;   RETN expmod 2
;; RETN expmod 4
;; 4

;; squareを使っていないため枝分かれが生じてしまい、 ;; 結果として計算量がlog_nではなく、nとなってしまう。

問題1.27

;; 問題1.27

(define (expmod base exp m)
  (define (square x)
    (* x x)) 
  (cond [(= exp 0) 1]
        [(even? exp)
         (remainder (square (expmod base (/ exp 2) m)) 
                    m)] 
        [else
         (remainder (* base (expmod base (- exp 1) m)) 
                    m)]))

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (define (iter-test a)
    (if (= a n)
        #t
        (and (try-it a)
             (iter-test (+ a 1)))))
  (iter-test 1))

(fermat-test 561)
;; gosh> #t
(fermat-test 1105)
;; gosh> #t
(fermat-test 1729)
;; gosh> #t
(fermat-test 2465)
;; gosh> #t
(fermat-test 2821)
;; gosh> #t
(fermat-test 6601)
;; gosh> #t

(fermat-test 10) ;; gosh> #f

問題1.28

この問題はとばしました。

問題1.29

;; 問題1.29
;; Simpsonの公式

(define (even? n)
  (= (remainder n 2) 0))

(define (cube n)
  (* n n n))

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

(define (simpson f a b n)
    (define (helper h)
      (/ (- b a) n))
    (define (next k)
      (+ k 1))
    (define (y k)
      (f (+ a (* k h))))
    (define (term k)
      (cond [(or (= 0 k) (= n k)) (y k)]
            [(even? k) (* 2 (y k))]
            [else (* 4 (y k))]))
    (* (sum term 0 next n)
       (/ helper 3)))


(simpson cube 0 1.0 100)
;; gosh> 0.24999999999999992
(simpson cube 0 1.0 1000) ;; gosh> 0.2500000000000003

問題1.30

;; 問題1.30
;; 手続きsumの反復化

;; 反復のsum
(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ result (term a)))))
    (iter a 0))

(define (sum-integers a b)
  (define (identity x) x)
  (define (inc x) (+ x 1))
  (sum identity a inc b))

(sum-integers 1 10)
;; gosh> 55


;; 比較のために再帰のsum
(define (recursion-sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (recursion-sum term (next a) next b))))

(define (recursion-sum-integers a b)
  (define (identity x) x)
  (define (inc x) (+ x 1))
  (recursion-sum identity a inc b))

(recursion-sum-integers 1 10)
;; gosh> 55

;; 計算量は変化なし ;; 再帰呼び出しがなくなるためにスペースが小さくて済む

次回

  • 1.31から1.34まで