7일차 - 1.3.1

1.3.1 프로시저를 인자로 받는 프로시저

ex 1.29

Simpson's rule은 f(x)를 a~b로 정적분하는 규칙으로, a, (a+b)/2, b의 3점을 지나는 Lagrange polynomial interpolation(2차 방정식) 하고, 이를 적분한 식으로부터 면적을 계산한다. f(x)의 a~b 구간을 2차 방정식으로 interpolation한 함수를 P(x)라고 하고, a와 b의 중간점((a+b)/2)을 m이라 하면, P(x)의 a~b 구간에서 적분값은 ((b - a) / 6) * (f(a) + 4f(m) + f(b)) 이다.

f(x)의 A~B 구간을 짝수인 n 구간(h=(B-A)/n)으로 나누고(나눈 위치를 x0(=A), x1, x2, ... xn(=B) 이라고 하고), 2 구간씩을 Simpson's rule에 따라 계산하면 정적분 값은 h/3 * (f(x0) + 4*f(x1) + 2*f(x2) + 4*f(x3) + 2*f(x4) + ... + 4*f(xn-1) + f(xn)) 이 되고 이를 SUM으로 표현하면, h/3 * (f(x0) + 4*SUM(f(x2i-1)) + 2*SUM(f(x2)) + f(n)) 이 된다.

SUM을 이용해서 integral-simpson 프로시저를 구할 때 sum 프로시저 호출 시 a와 b 인자를 어떻게 설정하는지에 따라 term과 next 프로시저를 다르게 짤 수 있다. 첫번째는 sum의 a 인자값을 실제 범위의 시작값으로 설정하고 next를 실제 간격만큼 증가시키도록 짠 것이고, 두번째 프로시저는 n만큼 반복한다고 생각하고 sum의 a=0, b=n으로 설정한 후 next 프로시저는 1씩 증가하는 inc 프로시저를 설정한 방법이다.

(integral-simpson cube 0 10 100)를 실행하면 모두 동일한 결과가 나오지만, 첫번째 방법은 내부 term 프로시저의 인자 x가 실수이고, 중간의 cond 조건 비교가 실수 비교를 하게 되므로 테스트 식처러 딱 나눠떨어지지 않는 경우 문제가 생길 수 있다. 또 정수 연산에 비해 속도가 느릴거라 생각된다. 즉 첫번째 보다는 두번째 방법이 더 좋은 방법이다.

;; 이건 a부터 시작해서 h만큼 늘어가는 방법
(define (integral-simpson f a b n)
  (define h (/ (- b a) n))
  (define (term x) ; x = a + kh
    (* (cond ((or (= x a) (= x b)) 1)
             ((odd? (/ (- x a) h)) 4)
             (else 2))
       (f x)))
  (define (next x)
    (+ x h))
  (* (/ h 3.0) (sum term a next b)))
;; (integral-simpson cube 0 10 100) => 2500.0

;; 이건 n만큼 돌린다고 생각하고 짠것. 
(define (integral-simpson-2 f a b n)
  (define h (/ (- b a) n))
  (define (term x)
    (* (cond ((or (= x 0) (= x n)) 1)
             ((odd? x) 4)
             (else 2))
       (f (+ a (* x h)))))
  (* (/ h 3.0) (sum term 0 inc n)))
;; (integral-simpson-2 cube 0 10 100) => 2500.0

ex 1.30

;; iterative process SUM 짜기
(define (sum-i term a next b)
  (define (iter x result)
    (if (> x b)
        result
        (iter (next x) (+ result (term x)))))
  (iter a 0))

;; iterative process sum 테스트
(define (sum-cubes-i a b)
  (sum-i cube a inc b))

ex 1.31

product를 차수높은 프로시저로 짜기

;; a - recursive process
(define (product-r term a next b)
  (if (> a b)
      1
      (* (term a) (product-r term (next a) next b))))
;; (product-r identify 1 inc 10) => 3628800

;; b - iterative process
(define (product-i term a next b)
  (define (iter x result)
    (if (> x b)
        result
        (iter (next x) (* result (term x)))))
  (iter a 1))
;; (product-i identify 1 inc 10) => 3628800

;; c - pi/4 계산하기
;; pi/4 = (2/3)*(4/3)*(4/5)*(6/5)*(6/7)*...
;; 분자는 2 4 4 6 6 8 8 ...
;; i가 홀수면 i+1, 짝수면 i+2
;; 분모는 3 3 5 5 7 7 9 9 ...
;; i가 홀수면 i+2, 짝수면 i+1
(define (pi-over-4 n)
  (define (term a)
    (/ (if (odd? a) (+ a 1.0) (+ a 2))
       (if (odd? a) (+ a 2.0) (+ a 1))))
  (product-i term 1 inc n))
;; (pi-over-4 1000000) => 0.7853985560957135
;; (/ pi 4) => 0.7853981633974483

ex 1.32

;; accumulate 짜기
;; recursive process
(define (accumulate-r combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a) (accumulate-r combiner null-value term (next a) next b))))
;; iterative process
(define (accumulate-i combiner null-value term a next b)
  (define (iter x result)
    (if (> x b)
        result
        (iter (next x) (combiner result (term x)))))
  (iter a null-value))

;; product
(define (product-a-r term a next b)
  (accumulate-r * 1 term a next b))
;; (product-a-r identify 1 inc 10) => 3628800
(define (product-a-i term a next b)
  (accumulate-i * 1 term a next b))
;; (product-a-i identify 1 inc 10) => 3628800

;; sum
(define (sum-a-r term a next b)
  (accumulate-r + 0 term a next b))
;; (sum-a-r identify 0 inc 10) => 55
(define (sum-a-i term a next b)
  (accumulate-i + 0 term a next b))
;; (sum-a-i identify 0 inc 10) => 55

ex 1.33

;; filtered-accumulate 짜고 책에 있는 a, b 짜기
(define (filtered-accumulate-r combiner null-value filter term a next b)
  (if (> a b)
      null-value
      (combiner (if (filter a)
                    (term a)
                    null-value)
                (filtered-accumulate-r combiner null-value filter term (next a) next b))))

(define (filtered-accumulate-i combiner null-value filter term a next b)
  (define (iter x result)
    (if (> x b)
        result
        (iter (next x) (combiner result (if (filter x) (term x) null-value)))))
  (iter a null-value))
 
;(filtered-accumulate-r + 0 even? identify 0 inc 10) ; => 30
;(filtered-accumulate-r + 0 odd? identify 0 inc 10)  ; => 25
;(filtered-accumulate-i + 0 even? identify 0 inc 10) ; => 30
;(filtered-accumulate-i + 0 odd? identify 0 inc 10)  ; => 25

(define (square x)
  (* x x))

(define (prime? n)
  (= (smallest-divisor n) n))

(define (smallest-divisor n)
  (define (divides? a b)
    (= (remainder a b) 0))
  (define (square x)
    (* x x))
  (define (find-divisor value test-div)
    (cond ((divides? value test-div) test-div)
          ((> (square test-div) value) value)
          (else (find-divisor value (+ test-div 1)))))
  (find-divisor n 2))

;; a
(define (sum-prime-square a b)
  (filtered-accumulate-i + 0 prime? square a inc b))

;; (sum-prime-square 2 10) => 2*2 + 3*3 + 5*5 + 7*7 = 87

(define (GCD a b)
  (if (= b 0)
      a
      (GCD b (remainder a b))))

;; b
(define (product-seed n)
  (define (filter x)
    (= (GCD x n) 1))
  (filtered-accumulate-i * 1 filter identify 1 inc (- n 1)))
;; (product-seed 10) ;; => (* 1 3 7 9) = 189