SICP: Exercise 1.22

2 年ぶりに SICP の記事を書くことになった。1 年半前の鬱々としていた日々がなければもっと早く進んだんだけどなぁ…

問題 1.22

殆んどの Lisp の実装には基本手続き runtime があり、システムが走った時間を（例えばマイクロ秒で）示す整数を返す。次の timed-prime-test 手続きは整数 \( n \) で呼び出されると、\( n \) を印字し、\( n \) が素数かどうかを調べ、\( n \) が素数なら手続きは三つの星印とテストに要した時間を印字する。

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))

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

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

この手続きを使い、指定範囲の連続する奇整数について素数性を調べる手続き search-for-primes を書け。その手続きで、それぞれ 1,000、10,000、100,000、1,000,000 より大きい、小さい方から三つの素数を見つけよ。素数をテストする時間に注意せよ。テストのアルゴリズムは \( \Theta(\sqrt{n}) \) の増加の程度だから、10,000 前後の素数のテストは 1,000 前後の素数のテストの \( \sqrt{10} \) 倍かかると考えよ。時間のデータはこれを支持するか。100,000、1,000,000 のデータは \( \sqrt{n} \) 予想のとおりだろうか。結果はプログラムが計算に必要なステップ数に比例した時間で走るという考えに合っているか。

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

Gauche で runtime を使えるようにする

「殆んどの Lisp の実装には基本手続き runtime があり」とあるが、Gauche にはなかった。「実行時間の計測 - n-oohiraのSICP日記」より以下を拝借。

(define (runtime)
  (use srfi-11)
  (let-values (((a b) (sys-gettimeofday)))
              (+ (* a 1000000) b)))

解答

素数は 2 以上なので、一応その範囲だけ調べるようにした。また、3 以上の素数は必ず奇数なので、奇数を調べた後は一つ置きに調べるようにした。

(define (search-for-primes start end)
  (cond ((> start end) 'finished)
        ((< start 2) (search-for-primes 2 end))
        (else (timed-prime-test start)
              (search-for-primes
                (+ start
                   (if (even? start) 1 2))
                end))))

結果

search-for-primes を評価すると以下のように出力される。

(search-for-primes 20 30)
; 20
; 21
; 23 *** 1
; 25
; 27
; 29 *** 2

長いので、1,000 以上のものは最初の素数 3 つのみ書くことにする。

(search-for-primes 1000 1050)
; 1009 *** 7
; 1013 *** 7
; 1019 *** 7

(search-for-primes 10000 10050)
; 10007 *** 20
; 10009 *** 20
; 10037 *** 21

(search-for-primes 100000 100050)
; 100003 *** 64
; 100019 *** 64
; 100043 *** 65

(search-for-primes 1000000 1000050)
; 1000003 *** 199
; 1000033 *** 209
; 1000037 *** 198

素数テストに要した時間 [μsec] は、オーダーが同じならばほぼ等しいので、上記の結果の平均をとってみると

• \( n \approx 1000 \)：7.0
• \( n \approx 10000 \)：20.7
• \( n \approx 100000 \)：64.7
• \( n \approx 1000000 \)：202.0

となった。一つ上のオーダーでの値との比を調べると

• \( \frac{20.7}{7.0} \approx 3.0 \)
• \( \frac{64.7}{20.7} \approx 3.13 \)
• \( \frac{202.7}{64.7} \approx 3.13 \)

となり、すべて \( \sqrt{10} \approx 3.16 \) に近い値だった。したがって \( \sqrt{n} \) 予想は成立しており、プログラムが計算に必要なステップ数に比例した時間で走るという考えに合っているといえる。

今回の範囲では \( \sqrt{n} \) 予想はずっと成立していたけれど、今より速度が出ない昔のコンピュータを使っていたらどうなるのだろうか。問題の最後の文を見ると、ちょっと引っかかる。