SICP: Exercise 1.23

問題 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 と違う事情を説明せよ。

「計算機プログラムの構造と解釈 第二版 1.2.6 例：素数性のテスト」より

解答

問題文の通りに next を定義し、(next test-divisor) を使うように修正する。

(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)))))

結果

問題 1.22 で調べた 12 個の素数について、改良した素数テストに要する時間を測った。

ochaochaocha3.hateblo.jp

(for-each timed-prime-test
          '(1009 1013 1019
            10007 10009 10037
            100003 100019 100043
            1000003 1000033 1000037))

結果を以下に示す。

素数：\( p \)	問題 1.22：\( t_\mathrm{A}/\mathrm{\mu s} \)	問題 1.23：\( t_\mathrm{B}/\mathrm{\mu s} \)	\( t_\mathrm{A} / t_\mathrm{B} \)
1,009	7	7	1.0
1,013	7	4	1.8
1,019	7	5	1.4
10,007	20	13	1.5
10,009	20	13	1.5
10,037	21	13	1.6
100,003	64	38	1.7
100,019	64	39	1.6
100,043	65	39	1.7
1,000,003	199	122	1.6
1,000,033	209	122	1.7
1,000,037	198	122	1.6

\( p \) が大きくなると \( t_\mathrm{A} / t_\mathrm{B} \) は 1.6〜1.7 で安定した。2 には届いていないが、ほぼ期待通りといえるだろう。遅くなった原因は、next 内の if や、next の呼び出し自体に時間を要するためと考えられる。