Serendip

Web Studio

問題1.24

計算量は Θ(log n) の増加なので 1,000:1,000,000 は 1:2 程度と予想される。
結果を見ると 1:4 ぐらいになっている。

(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 (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
  (if (fast-prime? n 1)
      (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 (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
          (remainder (* base (expmod base (- exp 1) m))
                     m))))

(define (random x)
  (modulo (sys-random) x))

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

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

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

(search-for-primes 1000 1100)
(search-for-primes 1000000 1000100)

gosh> 
1009 *** 11
1013 *** 9
1019 *** 9
1021 *** 9
1023
1031 *** 9
1033 *** 8
1035
1039 *** 8
1049 *** 8
1051 *** 9
1061 *** 8
1063 *** 8
1065
1069 *** 10
1087 *** 9
1091 *** 17
1093 *** 9
1097 *** 7#<undef>
gosh> 
1000003 *** 40
1000033 *** 30
1000037 *** 40
1000039 *** 49
1000081 *** 34
1000099 *** 38#<undef>

問題1.25

パス

問題1.26

square を使う代わりに * を使っている部分で2回 (expmod base (/ exp 2) m) が呼び出されている。

(* (expmod base (/ exp 2) m)
   (expmod base (/ exp 2) m))

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

posted with amazlet at 08.11.07

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

Amazon.co.jp で詳細を見る