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
