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.23" "Exercise 1.23")
解答例
あたらしいコード
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (next test-divisor)))))
(define (next n)
(if (= n 2)
3
(+ n 2)))
実行例
gosh> (search-for-primes 1000 3) 1001 1003 1005 1007 1009 *** #<time-duration 0.000052000> 1011 1013 *** #<time-duration 0.000051000> 1015 1017 1019 *** #<time-duration 0.000052000> done gosh> (search-for-primes 10000 3) 10001 10003 10005 10007 *** #<time-duration 0.000154000> 10009 *** #<time-duration 0.000158000> 10011 10013 10015 10017 10019 10021 10023 10025 10027 10029 10031 10033 10035 10037 *** #<time-duration 0.000149000> done gosh> (search-for-primes 100000 3) 100001 100003 *** #<time-duration 0.000470000> 100005 100007 100009 100011 100013 100015 100017 100019 *** #<time-duration 0.000471000> 100021 100023 100025 100027 100029 100031 100033 100035 100037 100039 100041 100043 *** #<time-duration 0.000476000> done gosh> (search-for-primes 1000000 3) 1000001 1000003 *** #<time-duration 0.001495000> 1000005 1000007 1000009 1000011 1000013 1000015 1000017 1000019 1000021 1000023 1000025 1000027 1000029 1000031 1000033 *** #<time-duration 0.001493000> 1000035 1000037 *** #<time-duration 0.001483000> done
時間データを比較すると、速度の比は 5/3 程度で 2 よりは小さい。これは、 テストのステップ数は半分になっているが、next 手続きで、n が 2 かどうか を毎回判定しているというオーバヘッドのためである。
コード
##(sicp-answer-code "ex-1.23.scm")
