Serendip

Web Studio

問題1.21

(define (square n)
  (* n 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 (prime? n)
  (= n (smallest-divisor n)))

(smallest-divisor 199)   ; 199
(smallest-divisor 1999)  ; 1999
(smallest-divisor 19999) ; 7

gosh> square
gosh> smallest-divisor
gosh> find-divisor
gosh> divides?
gosh> prime?
gosh> 199
gosh> 1999
gosh> 7

問題1.22

n が10倍になると要する時間はおよそ√10（≒3.162）倍となっている。

gauche での runtime は SICP第一章(23) : プログラムの実行時間を計測 – mahata_dev を参考にした。

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

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

(define (search-for-primes a b)
      (search-for-primes-iter a b))

(define (search-for-primes-iter a b)
  (if (< a b)
      (and (if (prime? a)
           (timed-prime-test a))
           (search-for-primes-iter (+ a 1) b))))

(search-for-primes 1000 1100)
(search-for-primes 10000 10100)
(search-for-primes 100000 100100)
(search-for-primes 1000000 1000100)

gosh> timed-prime-test
gosh> start-prime-test
gosh> report-prime
gosh> runtime
gosh> search-for-primes
gosh> search-for-primes-iter
gosh> 
1009 *** 15
1013 *** 13
1019 *** 12
1021 *** 12
1031 *** 13
1033 *** 13
1039 *** 13
1049 *** 13
1051 *** 12
1061 *** 13
1063 *** 13
1069 *** 13
1087 *** 13
1091 *** 14
1093 *** 13
1097 *** 14#<undef>
gosh> 
10007 *** 38
10009 *** 37
10037 *** 37
10039 *** 38
10061 *** 38
10067 *** 37
10069 *** 39
10079 *** 37
10091 *** 51
10093 *** 38
10099 *** 38#<undef>
gosh> 
100003 *** 117
100019 *** 117
100043 *** 115
100049 *** 115
100057 *** 115
100069 *** 114#<undef>
gosh> 
1000003 *** 357
1000033 *** 357
1000037 *** 359
1000039 *** 360
1000081 *** 421
1000099 *** 358#<undef>

問題1.23

計算速度の比はおよそ1.4〜1.6程度となっている。
ちょうど2倍とならないのは毎回途中で next 手続きが入るためか？

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

(search-for-primes 1000 1100)
(search-for-primes 10000 10100)
(search-for-primes 100000 100100)
(search-for-primes 1000000 1000100)

gosh> next
gosh> find-divisor
gosh> 
1009 *** 9
1013 *** 9
1019 *** 9
1021 *** 10
1031 *** 9
1033 *** 9
1039 *** 9
1049 *** 9
1051 *** 9
1061 *** 9
1063 *** 9
1069 *** 9
1087 *** 9
1091 *** 9
1093 *** 9
1097 *** 9#<undef>
gosh> 
10007 *** 24
10009 *** 26
10037 *** 25
10039 *** 25
10061 *** 25
10067 *** 24
10069 *** 25
10079 *** 25
10091 *** 24
10093 *** 25
10099 *** 24#<undef>
gosh> 
100003 *** 74
100019 *** 73
100043 *** 73
100049 *** 72
100057 *** 74
100069 *** 74#<undef>
gosh> 
1000003 *** 225
1000033 *** 227
1000037 *** 225
1000039 *** 225
1000081 *** 233
1000099 *** 230#<undef>

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る