第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まで