SICP 問題 1.23 （ムダを省いたアルゴリズムで再度時間の増加の程度を求める）
【問題】
本節の初めのsmallest-divisor は多くの不要な計算をする：
数が2で割り切れるか調べた後は、より大きい偶数で割り切れるか調べるのは無意味である。
test-divisor が使う値は 2, 3, 4, 5, 6, ... ではなく、2, 3, 5, 7, 9, ... であるべきだ。
この変更を実装するため、入力が 2 なら 3 を返し、そうでなければ入力に 2 足したものを返す手続き next を定義せよ。
smallest-divisorを、(+ test-divisor 1) ではなく、(next test-divisor) を使うように修正せよ。
このように修正したsmallest-divisor にした timed-prime-testで、問題 1.22 で見つけた12個の素数をテストせよ。
この修正はテストのステップを半分にしたので、二倍速く走ることが期待される。この期待は確かめられるか。
そうでなければ、得られた二つのアルゴリズムの速度の比はどうであったか。
それが２と違う事情を説明せよ。
【解答】
まずは使い勝手の為に前回の解答をきれいにまとめておく。
;最少の序数を求める (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 (square x) (* x x)) ; time-differenceを使用するため。 (use srfi-19) (define (timed-prime-test n) (newline) (display n) (start-prime-test n (current-time))) (define (start-prime-test n start-time) (if (prime? n) (report-prime (time-difference (current-time) start-time)))) (define (report-prime elapsed-time) (display " *** ") (display elapsed-time))
さて、next関数だけんども。こんな感じ。
(define (next x) (if (= 2 x) 3 (+ 2 x)))
次に、nextを使ってsmallest-divisorを修正しろと書いてあるが、これ多分、find-divisorの間違いじゃなかろうか。
;除数を求める処理 (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)))))
さ、実行してみよう。
gosh> (timed-prime-test 1009)1009 *** #
#
gosh> (timed-prime-test 1013)1013 *** #
#
gosh> (timed-prime-test 1019)1019 *** #
#
gosh> (timed-prime-test 10007)10007 *** #
#
gosh>
お？なんで時間ゼロなんだ？？おかしいな。
gosh> (timed-prime-test 1000039)1000039 *** #
#
gosh>
おいおい、でっかい数字でもゼロじゃねぇか。どーゆーこっちゃ？
next使わないやつに戻して評価してみよう。
gosh> (timed-prime-test 1000039)1000039 *** #
#
gosh>
あれ〜！？同じだ。じゃ、一昨日やったあの結果は一体。。
もっかいsearch-for-primeを読み込ませて動かしてみよう。
(define (search-for-primes idx max) (cond ((even? idx) (search-for-primes (+ idx 1) max)) ((> idx max) #f) (else (begin (timed-prime-test idx) (search-for-primes (+ idx 2) max)))))
gosh> (search-for-primes 1000 1020)1001
1003
1005
1007
1009 *** #
1011
1013 *** #
1015
1017
1019 *** ##f
gosh>
だめじゃん。なんで？素数の判別結果はちゃんと出てるのに、時間が。。
いやん。わからんちん。
つーわけで、答えが判別できませんのでこの問題は保留！
※2010/02/24 追記
(current-time)を実行したらちゃんと値が取れてそうだったので再度チャレンジしてみた。
gosh> (timed-prime-test 1009)1009 *** #
#
gosh> (timed-prime-test 1019)1019 *** #
#
gosh> (timed-prime-test 10007)10007 *** #
#
gosh> (timed-prime-test 1009)1009 *** #
#
gosh>
一発目はちゃんと差分時間が取れてるのに、なぜか２回目以降が昨日と同じ。。なぜだ？
かなり大きめの数字でやったらちゃんと出てるみたい。。
gosh> (search-for-primes 1000000000 1000000050)1000000001
1000000003
1000000005
1000000007 *** #
1000000009 *** #
1000000011
1000000013
1000000015
1000000017
1000000019
1000000021 *** #
1000000023
1000000025
1000000027
1000000029
1000000031
1000000033 *** #
1000000035
1000000037
1000000039
1000000041
1000000043
1000000045
1000000047
1000000049#f
gosh> (search-for-primes 10000000000 10000000050)10000000001
10000000003
10000000005
10000000007
10000000009
10000000011
10000000013
10000000015
10000000017
10000000019 *** #
10000000021
10000000023
10000000025
10000000027
10000000029
10000000031
10000000033 *** #
10000000035
10000000037
10000000039
10000000041
10000000043
10000000045
10000000047
10000000049#f
gosh>
でも、オーダーが同じなのに、ゼロで出るやつもあるなぁ。
gosh> (timed-prime-test 100000037)100000037 *** #
#
gosh> (timed-prime-test 100000039)100000039 *** #
#
gosh>
マジわかんねぇ。。
