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

7, 8일차

Announce/Chapter.1 2010.12.10 14:36
예정 범위 : 1.3.1 ~ 1.3.3

12월 14일 (화)
- 리뷰 : 전현철
- 발표 : 유승근

12월 16일 (목)
- 리뷰 : 이준
- 발표 : 유훈종
신고

6일차 review

Review 2010.12.09 23:42

1.2.6 연습:소수 찾기

소수 찾는 방법은 약수를 이용하는 방법과 페르마 검사를 이용한 확률적 방법 있다. 약수를 이용하는 방법은 계산 단계가 O(sqrt(n)) 이다.

확률적 방법에서는 새롭게 expmod 프로시저를 짜는데 이 프로시저를 주의해서 봐야 한다. expmod는 (base^exp)%m 을 계산하는 프로시저이고, 책에서는 다음과 같이 짜여 있다.

(define (expmod-1 base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m)) m))
        (else
         (remainder (* base (expmod base (- exp 1) m)) m))))

이 프로시저는 시간은 O(log n), 공간은 O(n)의 복잡도를 가진다. 기존에 짜여진 fastexpt-2 프로시저(연습 문제 1.16)를 이용하면 다음과 같이 짤 수 있고, 이 경우 시간은 O(log n), 공간은 O(1)의 복잡도를 가진다. 이 부분만 볼때는 fastexpt-2 프로시저를 이용하는 것이 좋아 보인다.

(define (expmod-2 base exp m)
  (remainder (fastexpt-2 base exp) m))

연습 문제 1.25가 이 질문인데 참고한 외부 솔루션을 기반으로 정리해 보면,
expmod-1의 경우는 연산을 계속 미루면서 공간이 늘어나는 대신 상태 변수의 값이 증가하지 않고 오히려 값이 감소하는 반면,
fastexpt-2의 경우는 내부 iteration을 돌면서 상태 변수 값이 계속 증가하게 된다.
이상적으로는 값이 크기가 기본 연산(primitive operator)의 실행 속도에 관련이 없어야겠지만, 실제로는 값이 커지면 기본 연산의 속도에 영향을 미치게 되므로 expmod-2가 아닌 expmod-1을 사용해야 한다라고 결론 내릴 수 있다.

expmod-1에 의한 계산 절차는 다음과 같다.

;; e : expmod-1
;; r : remainder
;; s : square
(e 10 20 3)
(r (s (e 10 10 3)) 3)
(r (s (r (s (e 10 5 3)) 3)) 3)
(r (s (r (s (* 10 (e 10 4 3))) 3)) 3)
(r (s (r (s (* 10 (r (s (e 10 2 3)) 3))) 3)) 3)
(r (s (r (s (* 10 (r (s (r (s (e 10 1 3)) 3)) 3))) 3)) 3)
(r (s (r (s (* 10 (r (s (r (s (r (* 10 (e 10 1 3)) 3)) 3)) 3))) 3)) 3)
(r (s (r (s (* 10 (r (s (r (s (r (* 10 (r (* 10 (e 10 0 3)) 3)) 3)) 3)) 3))) 3)) 3)
(r (s (r (s (* 10 (r (s (r (s (r (* 10 (r (* 10 1) 3)) 3)) 3)) 3))) 3)) 3)
(r (s (r (s (* 10 (r (s (r (s (r (* 10 (r 10 3)) 3)) 3)) 3))) 3)) 3)
(r (s (r (s (* 10 (r (s (r (s (r (* 10 1) 3)) 3)) 3))) 3)) 3)
(r (s (r (s (* 10 (r (s (r (s (r 10 3)) 3)) 3))) 3)) 3)
(r (s (r (s (* 10 (r (s (r (s 1) 3)) 3))) 3)) 3)
(r (s (r (s (* 10 (r (s (r 1 3)) 3))) 3)) 3)
(r (s (r (s (* 10 (r (s 1) 3))) 3)) 3)
(r (s (r (s (* 10 (r 1 3))) 3)) 3)
(r (s (r (s (* 10 1)) 3)) 3)
(r (s (r (s 10) 3)) 3)
(r (s (r 100 3)) 3)
(r (s 1) 3)
(r 1 3)
1

expmod-2에 의한 계산 절차는 다음과 같다.

;; iter는 내부에서 반복 프로세스로 동작하는 프로시저
(remainder (fastexpt-2 4 6) 3)
(iter 1 4 6)
(iter 1 16 3)
(iter 16 16 2)
(iter 16 256 1)
(iter 4096 256 0)
4096

프로세스와 같이 expmod-1은 공간은 늘어났다 줄어드는 반면, 값의 크지 않고,expmod-2는 공간의 동일하나 값이 계속 커진다.

저작자 표시 비영리
신고

티스토리 툴바