[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 個の素数をテストせよ. この修正はテストのステップを半分にしたので, 二倍速く走ることが期待される. この期待は確められるか. そうでなければ, 得られた二つのアルゴリズムの速度の比はどうであったか. それが2と違う事情を説明せよ.

問題文にあるように手続きを修正します.

(define (square x) (* x x))

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

;; 問題文により追加
(define (next n)
  (if (= n 2)
      3
      (+ n 2)))

(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 (smallest-divisor n)
  (find-divisor n 2))

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

;; 素数を求めるために必要な時間を計測する
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (current-milliseconds)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (current-milliseconds) start-time))))

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

(define (search-for-primes start end)
  (cond ((< start end)
         (timed-prime-test start)
         (search-for-primes (+ start 1) end))
        (else 
         (newline)
         (display "end"))))
 

問題 1.22で求めた12個の素数を判定するための時間を計測します.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (search-for-primes 100000000000000 100000000000100)
100000000000031 *** 624  (939)
100000000000067 *** 571  (1397)
100000000000097 *** 598  (949)
end
> (search-for-primes 1000000000000000 1000000000000200)
1000000000000037 *** 1907  (2891)
1000000000000091 *** 1965  (2928)
1000000000000159 *** 1877  (2919)
end
> (search-for-primes 10000000000000000 10000000000000100)
10000000000000061 *** 5925  (9149)
10000000000000069 *** 5887  (9166)
10000000000000079 *** 5887  (9174)
end
> 

カッコ内に問題 1.22で計測した時間を書いています. 問題 1.22の結果と見比べると, 時間は短くなっていますが, 半分とまでは言えません. 手続きnextでnが2であるかどうかを判定しているからでしょう.