理系学生日記

おまえはいつまで学生気分なのか

問題1-22

時間計るらしいけど、runtimeなんてねーよ、とかいう感じでネットの海をさ迷っていたら、答えをチラ見するはめになったとかそういう。

(use srfi-19)
(define (square x) (* x x))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
	((divides? test-divisor n) test-divisor)
	(else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (current-time)))

(define (start-prime-test n called-time)
  (if (prime? n)
      (report-prime (time-difference (current-time) called-time))
      #f))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time)
  #t
)

(define (search-for-primes start n)
  (cond ((= n 0) (newline))
	((divides? 2 start) (search-for-primes (+ start 1) n))
	((timed-prime-test start) (search-for-primes (+ start 2) (- n 1)))
	(else (search-for-primes (+ start 2) n))))

以上を定義した後で、

gosh> (search-for-primes 10000 3)
10001
10003
10005
10007 *** #<time-duration 0.000000000>
10009 *** #<time-duration 0.000000000>
10011
10013
10015
10017
10019
10021
10023
10025
10027
10029
10031
10033
10035
10037 *** #<time-duration 0.000000000>
#<undef>

時間計れてないwww
桁を大きくしてみる。

gosh> (search-for-primes 100000 3)
100001
100003 *** #<time-duration 0.000000000>
100005
100007
100009
100011
100013
100015
100017
100019 *** #<time-duration 0.001000000>
100021
100023
100025
100027
100029
100031
100033
100035
100037
100039
100041
100043 *** #<time-duration 0.000000000>
#<undef>

まだダメ。SICPが書かれたのがくそ前だから、今のプロセッサの速さとは合わない悪寒。

gosh> (search-for-primes 1000000 3)
100001
100003 *** #<time-duration 0.000000000>
100005
100007
100009
100011
100013
100015
100017
100019 *** #<time-duration 0.001000000>
100021
100023
100025
100027
100029
100031
100033
100035
100037
100039
100041
100043 *** #<time-duration 0.000000000>
#<undef>
gosh> 
1000001
1000003 *** #<time-duration 0.001000000>
1000005
1000007
1000009
1000011
1000013
1000015
1000017
1000019
1000021
1000023
1000025
1000027
1000029
1000031
1000033 *** #<time-duration 0.000000000>
1000035
1000037 *** #<time-duration 0.001000000>
#<undef>

O(\sqrt n)とか観測できません ><。桁数上げればいいんだけど。