6일차 - prime 계산 시간

연습문제 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))))