Chat (Lingr.com)
Informaiton
Daily
Column
- MySQL日本語の旅(5/1)
- アクセス向上秘伝(5/9)
- 一風変ったHaskellλ門(6/13)
- SICP Answer Book (5/31) 問題3.26追加
Zope Solution
Extra
アーカイブ
OSS案内所
Site Info
関連リンク
##(link2sicp "book-Z-H-11.html#%_thm_1.22" "Exercise 1.22")
解答例
Gauche には runtime という手続きではないので、srfi-19 モジュールの手続き current-time を利用する。
(use srfi-19)
すこしだけ、変更を加える
(define (timed-prime-test n)
(newline)
(display n)
(start-prime-test n (current-time)))
(define (start-prime-test n start-time)
(and (prime? n)
(report-prime (time-difference (current-time) start-time))))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time)
#t)
search-for-primes の定義は以下のとおり
(define (search-for-primes from n)
(cond ((= n 0) (newline) 'done)
((even? from) (search-for-primes (+ from 1) n))
((timed-prime-test from) (search-for-primes (+ from 2) (- n 1)))
(else (search-for-primes (+ from 2) n))))
実行例
gosh> (search-for-primes 1000 3) 1001 1003 1005 1007 1009 *** #<time-duration 0.000080000> 1011 1013 *** #<time-duration 0.000079000> 1015 1017 1019 *** #<time-duration 0.000095000> done gosh> (search-for-primes 10000 3) 10001 10003 10005 10007 *** #<time-duration 0.000250000> 10009 *** #<time-duration 0.000273000> 10011 10013 10015 10017 10019 10021 10023 10025 10027 10029 10031 10033 10035 10037 *** #<time-duration 0.000276000> done gosh> (search-for-primes 100000 3) 100001 100003 *** #<time-duration 0.000843000> 100005 100007 100009 100011 100013 100015 100017 100019 *** #<time-duration 0.000817000> 100021 100023 100025 100027 100029 100031 100033 100035 100037 100039 100041 100043 *** #<time-duration 0.000806000> done gosh> (search-for-primes 1000000 3) 1000001 1000003 *** #<time-duration 0.002689000> 1000005 1000007 1000009 1000011 1000013 1000015 1000017 1000019 1000021 1000023 1000025 1000027 1000029 1000031 1000033 *** #<time-duration 0.002586000> 1000035 1000037 *** #<time-duration 0.002628000> done
計測時間のデータを見るかぎり、n の大きさが10倍になると、計算に必要な時間は ほぼ√10倍になっている。計測データは、プログラムが計算に必要なステップ数に 比例した時間で走るという考え方を支持すると考えてよい。
コード
##(sicp-answer-code "ex-1.22.scm")
