[SICP] 問題 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より大きい, 小さい方から三つの素数を見つけよ. 素数をテストする時間に注意せよ. テストのアルゴリズムはΘ(√n)の増加の程度だから, 10,000前後の素数のテストは1,000前後の素数のテストの√10倍かかると考えよ. 時間のデータはこれを支持するか. 100,000, 1,000,000のデータは√n予想のとおりだろうか. 結果はプログラムが計算に必要なステップ数に比例した時間で走るという考えに合っているか.

手続きruntimeの代わりにcurrent-millisecondsを使います. 手続きは次のようになります.

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

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

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

問題文では, 素数を求める範囲を1000から始めていますが, 時間を計測できないため, もっと大きな数字から始めます. 測定結果は次のとおりです. 見やすいように, 不要な結果を削除しています.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (search-for-primes 100000000000 100000000100)
100000000003 *** 45
100000000019 *** 29
100000000057 *** 28
100000000063 *** 29
end
> (search-for-primes 1000000000000 1000000000100)
1000000000039 *** 97
1000000000061 *** 90
1000000000063 *** 90
end
> (search-for-primes 10000000000000 10000000000100)
10000000000037 *** 293
10000000000051 *** 302
10000000000099 *** 307
end
> (search-for-primes 100000000000000 100000000000100)
100000000000031 *** 939
100000000000067 *** 1397
100000000000097 *** 949
end
> (search-for-primes 1000000000000000 1000000000000200)
1000000000000037 *** 2891
1000000000000091 *** 2928
1000000000000159 *** 2919
end
> (search-for-primes 10000000000000000 10000000000000100)
10000000000000061 *** 9149
10000000000000069 *** 9166
10000000000000079 *** 9174
end

結果を見ると, nを１桁増やすと時間は約３倍になっており、 nを２桁増やすと時間は約10倍になっています. このことから, プログラムが計算に必要なステップ数に比例した時間で走るという考えに合っていると言えます.

問題文には, search-for-primesは「指定範囲の連続する奇整数について」とありますが, この条件を満たしていません. 実害はないのでこのままとします.