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

(prime?) 프로시저는 항상 소수를 검사하는 올바른 프로시저라고 하면...

(define (prime-by-fermat-all-number? n)
  (define (iter a)
    (if (< a 2) #t
        (if (= (expmod a n n) a) (iter (- a 1)) #f)))
  (iter (- n 1)))
 
(define (camichael-number? n)
  (and (not (prime? n)) (prime-by-fermat-all-number? n)))

; (camichael-number? 11)   => #f
; (camichael-number? 561)  => #t
; (camichael-number? 1105) => #t
; (camichael-number? 1729) => #t
; (camichael-number? 2465) => #t
; (camichael-number? 2821) => #t
; (camichael-number? 6601) => #t

연습문제 1.22

1,000,000,000까지는 sqrt(10), 약 3.2배 가량 증가하는데, 1,000,000,000 이후부터 급격히 증가(20배?). 그 이후로는 대략 비슷해 짐. 연습문제 1.25의 결론처럼 숫자가 커져 연산 속도에 영향을 미친거이라 생각됨.

; 1000           ***    0.004882812500 ***    0.005126953125 ***    0.006103515625
; 10000          ***    0.015869140625 ***    0.017822265625 ***    0.015869140625
; 100000         ***    0.052001953125 ***    0.049072265625 ***    0.051025390625
; 1000000        ***    0.157958984375 ***    0.160888671875 ***    0.162109375000
; 10000000       ***    0.492187500000 ***    0.503906250000 ***    0.485839843750
; 100000000      ***    1.593994140625 ***    2.043945312500 ***    1.531005859375
; 1000000000     ***    5.008789062500 ***    5.659179687500 ***    5.419921875000
; 10000000000    ***   92.404052734375 ***  154.035888671875 ***   91.474121093750
; 100000000000   ***  342.795898437500 ***  344.692138671875 ***  347.473876953125
; 1000000000000  *** 1128.643066406250 *** 1105.849121093750 *** 1112.751953125000
; 10000000000000 *** 3619.240966796875 *** 3515.051025390625 *** 4914.712890625000

연습문제 1.23

+1(연습문제 1.22)에 비해 절반 시간을 보임.

; 1000           ***    0.004150390625 ***    0.005126953125 ***    0.004150390625
; 10000          ***    0.011962890625 ***    0.011962890625 ***    0.012939453125
; 100000         ***    0.041015625000 ***    0.033935546875 ***    0.033935546875
; 1000000        ***    0.116943359375 ***    0.117187500000 ***    0.109863281250
; 10000000       ***    0.344970703125 ***    0.338867187500 ***    0.341796875000
; 100000000      ***    1.219970703125 ***    1.272949218750 ***    1.093994140625
; 1000000000     ***    3.734863281250 ***    3.724121093750 ***    3.524169921875
; 10000000000    ***   48.615966796875 ***   48.451904296875 ***   48.177001953125
; 100000000000   ***  231.741943359375 ***  167.779052734375 ***  173.546875000000
; 1000000000000  ***  631.395996093750 ***  591.827880859375 ***  621.291015625000
; 10000000000000 *** 1892.336181640625 *** 1906.916015625000 *** 1847.104980468750

연습문제 1.24

페르마 테스트를 이용한 prime 계산 시간. 1,000와 1,000,000의 계산 시간이 log n배 차이가 나는가? 그렇다. 참고로 내장된 random 프로시저가 1,000,000,000보다 큰 수에 대해서는 계산을 못하므로 에러 발생.

; 1000       *** 0.802001953125 *** 0.83300781250 *** 0.875976562500
; 10000      *** 1.072998046875 *** 1.02001953125 *** 1.052978515625
; 100000     *** 2.477050781250 *** 2.31689453125 *** 2.307861328125
; 1000000    *** 3.400146484375 *** 3.22607421875 *** 3.428955078125
; 10000000   *** 4.041992187500 *** 4.45117187500 *** 4.256103515625
; 100000000  *** 5.079101562500 *** 4.97900390625 *** 4.998046875000
; 1000000000 *** 5.583984375000 *** 5.29101562500 *** 5.474853515625

(runtime)

Racket에서 실행하려면 (runtime) 말고 (current-inexact-milliseconds)를 사용해야 한다.

;; 1.22
(define (timed-prime-test n)
;  (display n)
;  (newline)
  (start-prime-test n (current-inexact-milliseconds)))

(define (start-prime-test n start-time)
  (if (prime? n) ; 100)
      (report-prime n (- (current-inexact-milliseconds) start-time))
      #f))

(define (report-prime n elapsed-time)
  (display " *** ")
  (display elapsed-time))

(define (search-for-prime n c)
  (if (= c 0)
      (newline)
      (search-for-prime
       (+ n 1)
       (if (timed-prime-test n)
           (- c 1)
           c))))

1.2 프로시저와 프로세스

;
;; 어떤 문제를 풀기 위해 어떤 식으로 프로그래밍 언어를 써야 하는지 모르는 상태다.
;; 어떤 프로시저를 정의해야 하는데 프로시저를 돌릴 때 어떤 결과가 나오는지 미리 그려낼 줄 아는 경험 부족한 상태.
;; 프로시저: 한 컴퓨터 프로세스가 어떻게 나아가는지 밝힌 것.
;; 프로시저가 만들어내는 프로세스의 몇가지 꼴(shape)의 보기를 들것이다.
;

1.2.1 되돌거나 반복하는 프로세스

;
;; 되도는 프로세스 recursion
;;  - 연산을 바로 수행하지 못하고 뒤로 미루는(deferred operation) 모양
;; 반복하는 프로세스 iterative
;;  - 상태변수 존재. 계산의 크기가 늘어나지 않는다.
;; 되도는 프로세스와 되도는 프로시저
;;  - 프로시저는 되도는 모양이더라도(자신을 다시 호출) 프로세스는 그렇지 않을 수 있다. - linera iterative process
;; tail recursion : 꼬리에서 자기 자신을 다시 호출하면서 recursive process가 안되도록 하는 것.
;;  - http://en.wikipedia.org/wiki/Recursion_%28computer_science%29#Tail-recursive_functions

;; fact(n) = n * (n -1) * (n-2) * ... * 2 * 1
(define (fact1 n)
  (if (= n 1)
      1
      (* n (fact1 (- n 1)))))

;; recursive process
;; (fact1 4)
;; (* 4 (fact 3))
;; (* 4 (* 3 (fact 2)))
;; (* 4 (* 3 (* 2 (fact 1))))
;; (* 4 (* 3 (* 2 1)))
;; (* 4 (* 3 2))
;; (* 4 6)
;; 24

;; iterative process
;; product < counter * product
;; counter < counter - 1
(define (fact2 n)
  (define (iter p c)
    (if (= c 1)
      p
      (iter (* p c) (- c 1))))
  (iter 1 n))

;; (fact2 4)
;; (iter 1 4)
;; (iter 4 3)
;; (iter 12 2)
;; (iter 24 1)
;; 24

;; ex 1.9

;; (+ 4 5)
;; (inc (+ 3 5))
;; (inc (inc (+ 2 5)))
;; (inc (inc (inc (+ 1 5))))
;; (inc (inc (inc (inc (+ 0 5)))))
;; (inc (inc (inc (inc 5)))))
;; (inc (inc (inc 6)))
;; (inc (inc 7))
;; (inc 8)
;; 9

(define (inc a)
  (+ a 1))

(define (dec a)
  (- a 1))

(define (plus-1 a b)
  (if (= a 0)
      b
      (inc (plus-1 (dec a) b))))

;; (plus-1 2 3)
;; (inc (plus-1 1 3))
;; (inc (inc (plus-1 0 3)))
;; (inc (inc 3))
;; (inc 4)
;; 5

(define (plus-2 a b)
  (if (= a 0)
      b
      (plus-2 (dec a) (inc b))))
;; (plus-2 2 3)
;; (plus-2 1 4)
;; (plus-2 0 5)
;; 5

;; ex 1.10
;; 애커만 함수 http://en.wikipedia.org/wiki/Ackermann_function
;; primitive recursive function은 아니지만 total computable function
;; primitive recursive function은 항상 total computable function이다.
;; A(x, y)
;; 0                      if y = 0
;; 2 * y                  if x = 0
;; 2                      if y = 2
;; A(x - 1, A(x, y - 1))
(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

;; (A 0 n) : (* 2 n)
;; (A 1 n) : (exp 2 n)
;; (A 2 n) : n = 1 이면 1
;;           n > 1 이면 (exp 2 (exp 2 (exp 2 ... 2))) -> n번 반복
;; (A 3 n) : n = 1 이면 1
;;           n > 1 이면 ???
;

1.2.2 여러 갈래로 되도는 프로세스

;
;; 피보나치 수열 f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1
;;
;; 0 -> 0
;; 1 -> 1
;; recursive process
(define (fib1 n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib1 (- n 1)) (fib1 (- n 2))))))

;; fib1 -> n -> pi^n / root(5)

;; f(n) = f(n-1) + f(n-2)
;; iterative process
(define (fib2 n)
  (define (iter a b c)
    (if (= c 0)
        b
        (iter (+ a b) a (- c 1))))
  (iter 1 0 n))
;; (fib 4)
;; (iter 1 0 4)
;; (iter 1 1 3)
;; (iter 2 1 2)
;; (iter 3 2 1)
;; (iter 5 3 0)
;; 3

;; 돈 바꾸는 방법 ??? - review 할 때 다시 얘기해 봅시다.
;; 받은 돈을 동전으로 바꾸는 방법
;; 10 센트
;; 1 센트 * 10
;; 5 센트 * 2
;; 5 센트 + 1 센트 * 5

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount (- kinds-of-coins 1))
                 (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins)))))

(define (first-denomination kinds)
  (cond ((= kinds 1) 1)
        ((= kinds 2) 5)
        ((= kinds 3) 10)
        ((= kinds 4) 25)
        ((= kinds 5) 50)))

;; ex 1.11
(define (F1 n)
  (if (< n 3)
      n
      (+ (F1 (- n 1)) (* (F1 (- n 2)) 2) (* (F1 (- n 3)) 3))))

;; a < a + 2*b + 3c
;; b < a 
;; c < b
(define (F2 n)
  (define (iter x y z count)
    (if (< count 3)
        x
        (iter (+ x (* y 2) (* z 3)) x y (- count 1))))
  (iter 2 1 0 n))

;; f(0) = 0
;; f(1) = 1
;; f(2) = 2
;; f(3) = f(2) + 2f(1) + 3f(0) = 4

;; ex 1.12
;; pascal's triangle,
;; p(r, c) = p(r-1, c-1) + p(r-1, c)
;; p(r, 1) = 1, p(r, r) = 1
(define (pt r c)
  (cond ((or (= c 1) (= r c)) 1)
        ((or (< c 0) (< r 0) (> c r)) 0)
        (else (+ (pt (- r 1) (- c 1))
                 (pt (- r 1) c)))))
;