(define (cont-frac n d k)
  (define (cont-frac-helper i)
    (if (> i k)
        0
        (/ (n i) (+ (d i) (cont-frac-helper (+ i 1))))))
  (cont-frac-helper 1))

(define (ln-cf k)
  (define (n k) 1.0)
  (define (d k) (if (= (remainder (+ k 1) 3) 0) (* (/ (+ k 1) 3) 2) 1))
  (cont-frac n d k))

(ln-cf 10)

(define (tan-cf x k)
  (define (n k) (if ( = k 1) x (* x x)))
  (define (d k) (- (* 2 k) 1))
  (cont-frac n d k))

(tan-cf 0 10)
환영합니다. DrRacket, 버전 5.0.2 [3m].
언어: R5RS [사용자정의]; memory limit: 256 MB.
0.7182817182817183
0
>
신고

;; exercises 1.46

(define (iterative-improve f enough? first-guess)
  (define (iter guess)
    (if (enough? guess)
        guess
        (iter (f guess))))
  (iter first-guess))

(define (sqrt-iter-imp x)
  (iterative-improve (lambda (guess) (average guess (/ x guess)))
                     (lambda (guess) (< (abs (- (square guess) x)) 0.001))
                     1.0))
(define (fixed-point-iter-imp f first-guess)
  (iterative-improve f
                     (lambda (guess) (< (abs (- guess (f guess))) 0.001))
                     first-guess))

이건 내꺼

;; ex 1.46 - iterative-improve
(define (iterative-improve good? improve)
  (lambda (guess)
    (define (iter v)
      (if (good? v)
          v
          (iter (improve v))))
    (iter guess)))

;; sqrt
(define (sqrt-ii x)
  (define (good? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (/ (+ guess (/ x guess)) 2))
  ((iterative-improve good? improve) 1.0))

(sqrt-ii 9)

;; fixed-point
(define (fixed-point-ii f g)
  (define (good? guess)
    (< (abs (- guess (f guess)) 0.00001)))
  ((iterative-improve good? f) g))

(fixed-point cos 1.0)
신고

(define (inc x) (+ x 1))

(define (double f)
  (lambda (x) (f (f x))))

;; 맞바꿈 계산법으로 확인하기
(((double (double double)) inc) 5)

(((double (lambda (x) (double (double x)))) inc) 5)

(((lambda (y) ((lambda (x) (double (double x))) ((lambda (z) (double (double z))) y))) inc) 5)

(((lambda (x) (double (double x))) ((lambda (z) (double (double z))) inc)) 5)

(((lambda (x) (double (double x))) (double (double inc))) 5)

((double (double (double (double inc)))) 5)

((double (double (double (lambda (x) (inc (inc x)))))) 5)

((double (double (lambda (a)
                   ((lambda (x) (inc (inc x)))
                    ((lambda (x) (inc (inc x))) a))))) 5)

((double (lambda (b)
           ((lambda (a)
              ((lambda (x) (inc (inc x)))
               ((lambda (x) (inc (inc x))) a)))
            ((lambda (a)
               ((lambda (x) (inc (inc x)))
                ((lambda (x) (inc (inc x))) a))) b)))) 5)
((lambda (c)
   ((lambda (b)
      ((lambda (a)
         ((lambda (x) (inc (inc x)))
          ((lambda (x) (inc (inc x))) a)))
       ((lambda (a)
          ((lambda (x) (inc (inc x)))
           ((lambda (x) (inc (inc x))) a))) b)))
    ((lambda (b)
      ((lambda (a)
         ((lambda (x) (inc (inc x)))
          ((lambda (x) (inc (inc x))) a)))
       ((lambda (a)
          ((lambda (x) (inc (inc x)))
           ((lambda (x) (inc (inc x))) a))) b))) c))) 5)

((lambda (b)
   ((lambda (a)
      ((lambda (x) (inc (inc x)))
       ((lambda (x) (inc (inc x))) a)))
    ((lambda (a)
       ((lambda (x) (inc (inc x)))
        ((lambda (x) (inc (inc x))) a))) b)))
 ((lambda (b)
    ((lambda (a)
       ((lambda (x) (inc (inc x)))
        ((lambda (x) (inc (inc x))) a)))
     ((lambda (a)
        ((lambda (x) (inc (inc x)))
         ((lambda (x) (inc (inc x))) a))) b))) 5))

((lambda (b)
   ((lambda (a)
      ((lambda (x) (inc (inc x)))
       ((lambda (x) (inc (inc x))) a)))
    ((lambda (a)
       ((lambda (x) (inc (inc x)))
        ((lambda (x) (inc (inc x))) a))) b)))
 ((lambda (a)
    ((lambda (x) (inc (inc x)))
     ((lambda (x) (inc (inc x))) a)))
  ((lambda (a)
     ((lambda (x) (inc (inc x)))
      ((lambda (x) (inc (inc x))) a))) 5)))

((lambda (b)
   ((lambda (a)
      ((lambda (x) (inc (inc x)))
       ((lambda (x) (inc (inc x))) a)))
    ((lambda (a)
       ((lambda (x) (inc (inc x)))
        ((lambda (x) (inc (inc x))) a))) b)))
 ((lambda (a)
    ((lambda (x) (inc (inc x)))
     ((lambda (x) (inc (inc x))) a)))
  ((lambda (x) (inc (inc x)))
   ((lambda (x) (inc (inc x))) 5))))

((lambda (b)
   ((lambda (a)
      ((lambda (x) (inc (inc x)))
       ((lambda (x) (inc (inc x))) a)))
    ((lambda (a)
       ((lambda (x) (inc (inc x)))
        ((lambda (x) (inc (inc x))) a))) b)))
 ((lambda (a)
    ((lambda (x) (inc (inc x)))
     ((lambda (x) (inc (inc x))) a)))
  ((lambda (x) (inc (inc x)))
   (inc (inc 5)))))

((lambda (b)
   ((lambda (a)
      ((lambda (x) (inc (inc x)))
       ((lambda (x) (inc (inc x))) a)))
    ((lambda (a)
       ((lambda (x) (inc (inc x)))
        ((lambda (x) (inc (inc x))) a))) b)))
 ((lambda (a)
     ((lambda (x) (inc (inc x)))
      ((lambda (x) (inc (inc x))) a)))
   (inc (inc (inc (inc 5))))))

((lambda (b)
   ((lambda (a)
      ((lambda (x) (inc (inc x)))
       ((lambda (x) (inc (inc x))) a)))
    ((lambda (a)
       ((lambda (x) (inc (inc x)))
        ((lambda (x) (inc (inc x))) a))) b)))
 ((lambda (x) (inc (inc x)))
      ((lambda (x) (inc (inc x))) (inc (inc (inc (inc 5)))))))

((lambda (b)
   ((lambda (a)
      ((lambda (x) (inc (inc x)))
       ((lambda (x) (inc (inc x))) a)))
    ((lambda (a)
       ((lambda (x) (inc (inc x)))
        ((lambda (x) (inc (inc x))) a))) b)))
 ((lambda (x) (inc (inc x)))
      (inc (inc (inc (inc (inc (inc 5))))))))

((lambda (b)
   ((lambda (a)
      ((lambda (x) (inc (inc x)))
       ((lambda (x) (inc (inc x))) a)))
    ((lambda (a)
       ((lambda (x) (inc (inc x)))
        ((lambda (x) (inc (inc x))) a))) b)))
 (inc (inc (inc (inc (inc (inc (inc (inc 5)))))))))

((lambda (a)
   ((lambda (x) (inc (inc x)))
    ((lambda (x) (inc (inc x))) a)))
 ((lambda (a)
    ((lambda (x) (inc (inc x)))
     ((lambda (x) (inc (inc x))) a))) (inc (inc (inc (inc (inc (inc (inc (inc 5))))))))))

((lambda (a)
   ((lambda (x) (inc (inc x)))
    ((lambda (x) (inc (inc x))) a)))
 ((lambda (x) (inc (inc x)))
   ((lambda (x) (inc (inc x))) (inc (inc (inc (inc (inc (inc (inc (inc 5))))))))))) 

((lambda (a)
   ((lambda (x) (inc (inc x)))
    ((lambda (x) (inc (inc x))) a)))
 ((lambda (x) (inc (inc x)))
   (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc 5)))))))))))) 

((lambda (a)
   ((lambda (x) (inc (inc x)))
    ((lambda (x) (inc (inc x))) a)))
 (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc 5)))))))))))))

((lambda (x) (inc (inc x)))
 ((lambda (x) (inc (inc x))) (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc 5))))))))))))))

(inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc 5))))))))))))))))

결론: double에 double을 적용하면 제곱으로 늘어남. (((double (double (double double))) inc) 0) ;; => 256

저작자 표시 비영리
신고

ex 1.42
(define (compose f g)
  (lambda (x) (f (g x))))

((compose square inc) 6) ;; => 49
ex 1.43
(define (repeated f i)
  (define (iter g n)
    (if (= n 1)
      g
      (iter (compose g f) (- n 1))))
  (iter f i))
((repeated inc 10) 0) ;; => 10
((repeated square 2) 5) ;; => (square (square 5)) => 625
ex 1.44
(define (smooth f)
  (lambda (x) (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3)))

(define (smooth-n f n)
  ((repeated smooth n) f))
ex 1.45
(define (cube-root x)
  (fixed-point (average-damp (lambda (y) (/ x (square y)))) 1.0))
;; (cube-root 27)

(define (4th-root x)
  (fixed-point (average-damp (lambda (y) (/ x (* y y y)))) 1.0))
;; (4th-root 16) => infinite loop

;; y -> x/y^(n-1) 은 몇번 average-damp 해야 하는지 실험하기
(define (nth-root x n)
  (fixed-point ((repeated average-damp n) (lambda (y) (/ x (expt y (- n 1)))))
               1.0))

;; 실험 결과.. 패턴이 안보인다
;; n = 4 > 2
;; n = 5 > 2
;; n = 13 > 3
;; n = 22 > 2
저작자 표시 비영리
신고

(작성중)


신고

1.35
(define golden-ratio 
    (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0))

golden-ratio
;; 1.6180327868852458
;; 1.36

(define tolerance 0.00001)
 
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)    
    (let ((next (f guess)))
      (display guess)
      (newline)
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(fixed-point (lambda (x) (/ (log 1000) (log x))) 4)
;; 4
;; 4.9828921423310435
;; 4.301189432497896
;; 4.734933901055578
;; 4.442378437719527
;; 4.632377941509957
;; 4.505830646780214
;; 4.588735606875765
;; 4.533824356566502
;; 4.569933524181419
;; 4.546075272637248
;; 4.561789745175653
;; 4.551417836654131
;; 4.558254212070262
;; 4.553744140202578
;; 4.556717747893265
;; 4.554756404545319
;; 4.5560497413912975
;; 4.5551967522618035
;; 4.555759257615811
;; 4.555388284933278
;; 4.555632929754932
;; 4.555471588998784
;; 4.555577989320218
;; 4.555507819903776
;; 4.555554095154945
;; 4.555523577416557
;; 4.555543703263474
;; 4.555530430629037
;; 4.555539183677709

(fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 4)
;; 4
;; 4.491446071165521
;; 4.5449746509755515
;; 4.553746974742814
;; 4.555231425802502
;; 4.555483906560562
;; 4.5555268862194875
;; 4.5555342036887705
;; 1.37
신고

예정 범위 : 1.3.3 ~ 1.3.4

12월 21일 (화)
- 리뷰 : 이준
- 발표 : 정다정(p88 ~ )

12월 23일 (목)
- 리뷰 : 정승희
- 발표 : 전현철

12월 28일 (화)
- 리뷰 : 정다정
- 특강 : 정다정
신고

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))))
저작자 표시 비영리
신고

티스토리 툴바