問題1.21~問題1.23
問題1.21
> (smallest-divisor 199) 199 > (smallest-divisor 1999) 1999 > (smallest-divisor 19999) 7
問題1.22
(define (search-for-primes n m) (cond ((< m n)(newline) 'done) ((timed-prime-test n)(search-for-primes (+ n 1) m)) (else (search-for-primes (+ n 1) m))))
上は間違いではないですが、最後の処理は無駄です。
下の処理でも正しく動作します。
(define (search-for-primes n m) (cond ((< m n)(newline) 'done) ((timed-prime-test n)(search-for-primes (+ n 1) m))))
注意
ここでのcondの使い方にとまどいました。
下の例のように、#tでない9でも、ifでは真として分岐しています。
ifやcondにおいては、#f以外は全て真として扱われるようです。
そのため問題22においては、timed-prime-testの結果によらず、必ずsearch-for-primesが実行されます。
> (if 9 'true 'false) 'true > (boolean? 9) #f
素数はそれぞれ以下の通りです。デスクトップマシンだと性能がよすぎていずれも処理時間が0となるため、ノートPCでtimed-prime-testとして改めて実行しました。
> (timed-prime-test 1009) 1009 *** 10 > (timed-prime-test 1013) 1013 *** 10 > (timed-prime-test 1019) 1019 *** 10 > (timed-prime-test 10007) 10007 *** 24 > (timed-prime-test 10009) 10009 *** 22 > (timed-prime-test 10037) 10037 *** 22 > (timed-prime-test 100003) 100003 *** 61 > (timed-prime-test 100019) 100019 *** 69 > (timed-prime-test 100043) 100043 *** 60 > (timed-prime-test 1000003) 1000003 *** 187 > (timed-prime-test 1000033) 1000033 *** 215 > (timed-prime-test 1000037) 1000037 *** 354
nが10倍になるとおおよそ3倍程度の時間がかかっていることから、√10倍と考えて問題ない結果になりました。
この結果からプログラムは、計算に必要なステップ数に比例した時間で走ると考えられます。
問題1.23
(define (next n) (if (= n 2) 3 (+ n 2)))
> (timed-prime-test 1009) 1009 *** 112 > (timed-prime-test 1013) 1013 *** 10 > (timed-prime-test 10007) 10007 *** 17 > (timed-prime-test 10009) 10009 *** 23 > (timed-prime-test 10037) 10037 *** 17 > (timed-prime-test 100003) 100003 *** 39 > (timed-prime-test 1000019) 1000019 > (timed-prime-test 100019) 100019 *** 39 > (timed-prime-test 100043) 100043 *** 43 > (timed-prime-test 1000003) 1000003 *** 114 > (timed-prime-test 1000033) 1000033 *** 130 > (timed-prime-test 1000037) 1000037 *** 130 >
nが大きい場合だと確かに早くはなっていますが、2倍にまではなっていません。
これはnextの処理において、nが2がどうかの判定処理を毎回実施しているのが理由です。
（プログラムの実行速度に関して、その処理時間をプログラムの実行内容から説明ができるのに感動しました。）
