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