問題1-21〜23

今日は、素数に関するトピックの後に掲載されている問題に取り組みました。アルゴリズムの違いによって計算量や処理時間にどのくらいの差が生じるかをテストする問題が含まれていたからです。しかし、DrSchemeでは本書に書かれているruntimeやrandomといった基本手続きを使えなかったため、具体的な時間を割り出すことはできませんでした。もっとエレガントな書き方があることは間違いありませんが、とりあえず現時点での自分がどんなコードを書いたのかを振り返られるようにするために、以下にまとめてみようと思います。

まずは、渡された値が素数かどうかを判別する手続きです。(問題1-21／本書のコードをコピー)

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

(define (smallest-divisor n)
  (find-divisor n 2))

(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 (divides? a b)
  (= (remainder b a) 0))

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

(prime? 15)
(smallest-divisor 199)
(smallest-divisor 1999)
(smallest-divisor 19999)

次は、渡された範囲内の整数の中から素数を抽出する手続きです。(問題1-22／時間測定はなし)

(define (prime-range-display from to)
  (prime-range-iter from to))

(define (prime-range-iter tgt to)
  (cond ((> tgt to) (finish-display))
        ((= tgt 1) (prime-range-iter (+ tgt 1) to))
        ((and (= (remainder tgt 2) 0) (> tgt 2))
         (prime-range-iter (+ tgt 1) to))
        (else (prime-check tgt)
              (prime-range-iter (+ tgt 1) to))))

(define (prime-check n)
  (if (prime? n)
      (prime-display n)))

(define (prime-display n)
  (newline)
  (display n)
  (display " is PRIME"))

(define (finish-display)
  (newline)
  (display " ** finish! ** "))

(prime-range-display 10000 100000)

最後は、素数判定手続きの中からムダを省いたバージョンです。(問題1-23)

(define (find-divisor n test-divisor)
  (define (next tgt)
    (cond ((= tgt 2) 3)
          ((= (remainder tgt 2) 0) (+ tgt 2))
          (else (+ tgt 1))))
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (next test-divisor)))))

実行結果を眺めながら、素数は少ないと思っていたけれども、意外と多くあるのだということに驚きました。また、runtimeやrandomに相当するような処理を書くためにはどうすればいいのかということをウェブで調べていたら、本書の問題に取り組み、その経緯をブログに書き記している人が少なからずいるということ発見することができました。そこには答えだけが書かれているのではなく、そこに至った経緯や、その人なりの追加課題に挑戦している様子が記されていて、こういう情報を上手いこと収集しながら、自分の知見を広められたら良いなと思っています。