SICPゼミ第3回 - SICPゼミ

読んでるpdf

練習問題1.17

対数時間で掛け算を定義せよ(再帰的に)

(define (fast-prod b n)
  (define (even? a)
    (= (remainder a 2) 0))
  (define (double a) (* 2 a))
  (define (halve a) (/ a 2))
  (cond ((= n 0) 0)
        ((even? n) (double (fast-prod b (halve n))))
        (else (+ b (fast-prod b (- n 1))))))

練習問題1.18

1.16,1.17を参考に掛け算を反復プロセスで定義

(define (fast-prod b n)
  (define (double a) (* 2 a))
  (define (fast-prod-iter count prod)
    (cond ((= 0 n) 0)
          ((= n count) prod)
          ((<= (double count) n) (fast-prod-iter (double count) (double prod)))
          (else (fast-prod-iter (+ count 1) (+ prod b)))))
  (fast-prod-iter 1 b))

イテレータ上から回さないと対数時間にならなくねと言われたので書き直し

(define (fast-prod b n)
  (define (double a) (* 2 a))
  (define (halve a) (/ a 2))
  (define (even? a) (= (remainder a 2) 0))
  (define (fast-prod-iter count prod)
    (cond ((= count 0) prod)
          ((even? count) (fast-prod-iter (halve count) (double prod)))
          (else (fast-prod-iter (- count 1) (+ prod b)))))
  (fast-prod-iter n 0))

練習問題1.19

(define (square n) (* n n))
(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        (( even? count)
         (fib-iter a
                   b
                   (+
                    (square p)
                    (square q))
                   (+
                    (* 2 p q)
                    (square q))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

練習問題1.20

f:id:sicp-zemi:20160302145048j:plain
正規順序評価だと18回，適用順序評価だと4回．
””””適用順序評価は神””””

練習問題1.21

以下のプログラムを199,1999,19999に関して実行する

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

結果は以下のとおり

gosh> (smallest-divisor 199)
199
gosh> (smallest-divisor 1999)
1999
gosh> (smallest-divisor 19999)
7

練習問題1.22

指定した範囲の連続した奇数について素数判定を行う手続きsearch-for-primes を書け。その手続きを使って、1000, 10,000, 100,000 より大きな素数をそれぞれ3つ見つけよ。
gaucheの処理系だとまずpdfにある(runtime)がなかったから代わりに(time->seconds (current-time))で実装した。
gaucheの処理系はクソなので副作用しかない関数を呼ぶとundefが返って死ぬのでstart-prime-testをifでなくandにすることで真偽値を返すようにした。

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

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (time->seconds (current-time))))

(define (start-prime-test n start-time)
  (and (prime? n)
      (report-prime (- (time->seconds (current-time)) start-time ))))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time ))

(define (search-for-primes n count)
  (define (even? m) (= (remainder m 2) 0))
  (define (search-iter m counter)
    (cond ((= counter count) (newline))
          ((even? m) (search-iter (+ m 1) counter))
          ((not (prime? m)) (search-iter (+ m 2) counter))
          ((timed-prime-test m) (search-iter (+ m 2) (+ counter 1)))
          (else (search-iter (+ m 2) counter))))
  (search-iter n 0))

gosh> (search-for-primes 1000 3)

1009 *** 1.0967254638671875e-5
1013 *** 7.867813110351562e-6
1019 *** 6.9141387939453125e-6
#<undef>
gosh> (search-for-primes 10000 3)

10007 *** 2.193450927734375e-5
10009 *** 2.002716064453125e-5
10037 *** 1.9073486328125e-5
#<undef>
gosh> (search-for-primes 100000 3)

100003 *** 5.888938903808594e-5
100019 *** 5.817413330078125e-5
100043 *** 5.817413330078125e-5
#<undef>

練習問題1.25

呼び出しのたびに剰余を計算しているexpmodと違ってexptを使うと一気に指数計算をしたのちに剰余を計算するのでexptの返り値がクソデカくなって落ちる。

練習問題1.26

expmodを一回呼び出す度に、元のアルゴリズムと比較して二倍の回数expmodが呼び出されているため、木のサイズが指数関数的に増える。もとのアルゴリズムがlog(n)オーダーだったのと比べその指数関数、つまりnオーダーのアルゴリズムになる。

練習問題1.27

カーマイケル数がフェルマーテストを騙すことを検証する
以下のプログラムはフェルマーテストを通る(素数かカーマイケル数である)ならば0，通らない(非素数である)ならば1を返す

(define (fermat-test n)
	(fermat-iter n 1))

(define 
	(fermat-iter n count)
	(cond
		((= count n) 0)
		((= (expmod count n n) count) (fermat-iter n (+ count 1)))
		(else 1)))

やってみた

gosh> (fermat-test 2)
0
gosh> (fermat-test 4)
1
gosh> (fermat-test 5)
0
gosh> (fermat-test 6)
1
gosh> (fermat-test 561)
0
gosh> (fermat-test 555)
1
gosh> (fermat-test 1105)
0

練習問題1.28

カーマイケル数絶対殺すマン

(define (expmod base exp m)
  (cond
   ((= exp 0) 1)
   (( even? exp)
    (if (and (= (remainder (square (expmod base (/ exp 2) m)) m) 1)
             (not (= (expmod base (/ exp 2) m) 1))
             (not (= (expmod base (/ exp 2) m) (- m 1))))
        0
      (remainder (square (expmod base (/ exp 2) m)) m)))
   (else (remainder (* base (expmod base (- exp 1) m)) m))))

殺した

gosh> (fermat-test 561)
1