SICP

SICP を読んでみる #12 第一章 p.30

問題解答

問1.23
next の定義。

(define (next n)
  (if (= n 2)
      3
      (+ n 2)))

next を使って find-divisor をかきかえる

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

処理時間の比較。最近の計算機だと処理速度が速すぎて小さい値だと正確な処理時間が測れないようなので、大きめの値を使用。

改良前
1000000021 *** 20519#
100000000003 *** 267726#

改良後
1000000021 *** 18565#
100000000003 *** 164153#

処理時間はそれぞれ 0.9 倍、 0.61 倍となっており、 半分にはならない。

明確な理由がわからなかったので先人知恵を借りる。
計算以外の、処理系のオーバーヘッドが大きな影響を及ぼしているっぽい。言われてみれば確かにそうか。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です