読者です 読者をやめる 読者になる 読者になる

SICP 演習問題 1.2

SICP

 

Exercise 1.9

(define (+ a b)
(if (= a 0) b (inc (+ (dec a) b))))

(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6))
(inc (inc 7)
(inc 8)
9

再帰

(define (+ a b)
(if (= a 0) b (+ (dec a) (inc b))))

(+ 4 5)
(+ (dec 4) (inc 5))
(+ 3 (inc 5))
(+ (dec 3) (inc (inc 5)))
(+ 2 (inc(inc 5)))
(+ (dec 2) (inc (inc (inc 5))))
(+ 1 (inc (inc (inc 5))))
(+ (dec 1) (inc (inc (inc (inc 5)))))
(+ 0 (inc (inc (inc (inc 5)))))
(inc (inc (inc (inc 5))))
9

反復

Exercise 1.10

(A 1 10)
(A 0 (A 1 9)
(A 0 (A 0 A(1 8)))
(A 0 (A 0 A(0 A(1 7))))
...
1024
(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (* 2 2)))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
...
2^16

 

(A 3 3)
(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
(A 2 (A 1 (A 2 1)))
(A 2 (A 1 2))
(A 2 (A 0 (A 1 1)))
(A 2 (A 0 2))
(A 2 4)
...
2^16

 

(define (f n) (A 0 n))
(f n) -> 2n

(define (g n) (A 1 n))
(g n) -> 2^n

(define (h n) (A 2 n))
(h n) -> 2^(2^n)

2の2のn乗乗??

Exercise 1.11

(define (f n)
(cond (< n 3) n)
(else (+ (f (- n 1)) (f (- n 2)) (f (- n 3))))
)

Excercise 1.12

#lang racket
(define (pascal x y)
(cond ((< y 1) 0)
((> y x) 0)
((= y 1) 1)
((= y x) 1)
(else (+ (pascal (- x 1) (- y 1))
(pascal (- x 1) y)))))

Exercise 1.13

Fib(0)=0
Fib(1)=1
Fib(n)=Fib(n-1)+Fib(n-2)

Fib(n)=(φ^(n) - ψ^(n))/a
( a = 5^(1/2) )
を証明
n=0のとき、n=1のとき、成立
Fib(k) = (φ^(k) - ψ^(k))/a
Fib(k+1) = (φ^(k+1) - ψ^(k+1))/a
が成立すると仮定して、
Fib(k+2)のとき
Fib(k+2)=(φ^(k+2) - ψ^(k+2))/a
を示す.
Fib(n+2)
= ( φ^(n+1) - ψ^(n+1) + φ^(n) - ψ^(n) )/a
= ( φ^n(φ+1)-ψ^n(ψ+1) )/a
= (φ^(k+2) - ψ^(k+2))/a
∵ φ+1 = φ^2 , ψ+1 = ψ^2

よって帰納法により、
Fib(n)=(φ^(n) - ψ^(n))/a

Exercise 1.14

はれないので省略

Exercise 1.15

12.15/3 = 4.05
4.05/3 = 1.35
1.35/3 = 0.45
0.45/3 = 0.15
0.15/3 = 0.03

4回

aに対しては3を底とする対数のオーダーなのでO(logn)となる。

 

Exercise 1.16

(define (fast-expt b n)
(expt-iter 1 b n ))
(define (expt-iter a b n)
(cond ((= n 0) a)
((even? n) (expt-iter (* (square b) a) b (/ n 2)))
(else (expt-iter (* b a) b (- n 1)))))

Exercise 1.17

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

Exercise 1.18

(define (fast-* a b c)
(cond (= b 0) 0
(even? n) (* a (halve b) (+ (double a) c) )
(else (* a (- b 1) (+ a c) ))))

Exercise 1.19

a <- bq + aq + ap
b <- bp + aq

a <- (bp+aq)q + (bq + aq + ap)q + (bq + aq + ap)p
= bpq + aq^2 + bq^2 + aq^2 + apq + bpq + apq + ap^2
= b(2pq + q^2) + a(2q^2 + 2pq + p^2)
= b(2pq + q^2) + a(2pq+q^2) + a(q^2+p^2)

b <- (bp + aq)p + (bq + aq + ap)q
= b(p^2 + q^2) + a(2pq + q^2)
i.e.
P' = (p^2 + q^2)
q' = (2pq + q^2)
(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
(+ (* p p) (* q q))
(+ (* 2 p q) (* q q))
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b q) (* a q))
p
q
(- count 1)))))

Exercise 1.20

(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))

適用順

(gcd 206 40)
(gcd 40 (remainder 206 40))
(gcd 40 6)
(gcd 6 (remainder 40 6))
(gcd 6 4)
(gcd 4 (remainder 6 4))
(gcd 4 2)
(gcd 2 (remainder 4 2))
(gcd 2 0)
2

正規化順

(gcd 206 40)
(gcd 40 (remainder 206 40))
(if (= (remainder 206 40) 0)
40
(gcd (remainder 206 40) (remainder 40 (remainder 206 40))))
(if (= 6 0)
40
(gcd (remainder 206 40) (remainder 40 (remainder 206 40))))
(gcd (remainder 206 40) (remainder 40 (remainder 206 40))))
(if (= (remainder 40 (remainder 206 40)) 0)
(remainder 206 40)
(gcd (remainder 40 (remainder 206 40))
(remainde 6 (remainder 40 (remainder 206 40)))))

Exercise 1.21

#lang racket
(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 (next test-divisor)))))

(define (divides? a b) (= (remainder b a) 0))

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

(define (square n) (* n n))

(define (next n) (+ n 1))

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

 

Exercise 1.22

#lang Racket
(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 (next test-divisor)))))
(define (divides? a b) (= (remainder b a) 0))
(define (prime? n) (= n (smallest-divisor n)))
(define (square n) (* n n))
(define (next n) (+ n 1))

(define (timed-prime-test n)
(newline) (display n) (start-prime-test n (current-inexact-milliseconds)))

(define (start-prime-test n start-time)
(if (prime? n) (report-prime (- (current-inexact-milliseconds) start-time)) -1))

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

(define (runtime) (current-milliseconds))
(timed-prime-test 1009)
(timed-prime-test 1013)
(timed-prime-test 1019)
(timed-prime-test 10007)
(timed-prime-test 10009)
(timed-prime-test 10037)
(timed-prime-test 100003)
(timed-prime-test 100019)
(timed-prime-test 100043)
(timed-prime-test 1000003)
(timed-prime-test 1000033)
(timed-prime-test 1000037)

結果

1009 *** 0.1689453125
1013 *** 0.004150390625
1019 *** 0.00390625
10007 *** 0.01220703125
10009 *** 0.010986328125
10037 *** 0.010986328125
100003 *** 0.031982421875
100019 *** 0.031982421875
100043 *** 0.031982421875
1000003 *** 0.10009765625
1000033 *** 0.10009765625
1000037 *** 0.10009765625

1009だけ異様に遅い。。。

他はおおむね理論通り。

Exercise 1.23

#lang racket
(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 (next test-divisor)))))

(define (divides? a b) (= (remainder b a) 0))

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

(define (square n) (* n n))

(define (next n)
(cond ((= n 2) 3)
(else (+ n 2))))
(define (timed-prime-test n)
(newline) (display n) (start-prime-test n (current-inexact-milliseconds)))

(define (start-prime-test n start-time)
(if (prime? n) (report-prime (- (current-inexact-milliseconds) start-time)) -1))

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

(timed-prime-test 1009)
(timed-prime-test 1013)
(timed-prime-test 1019)
(timed-prime-test 10007)
(timed-prime-test 10009)
(timed-prime-test 10037)
(timed-prime-test 100003)
(timed-prime-test 100019)
(timed-prime-test 100043)
(timed-prime-test 1000003)
(timed-prime-test 1000033)
(timed-prime-test 1000037)

結果

1009 *** 0.200927734375
1013 *** 0.003173828125
1019 *** 0.0029296875
10007 *** 0.007080078125
10009 *** 0.005859375
10037 *** 0.007080078125
100003 *** 0.01904296875
100019 *** 0.01904296875
100043 *** 0.02001953125
1000003 *** 0.06005859375
1000033 *** 0.06005859375
1000037 *** 0.05908203125

半分ではなく、3:2ぐらいの減り具合。   これは(next n) のオーバヘッドのせいではないか。

Exercise 1.24

#lang Racket
(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 (square a) (* a a))

(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) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))
(define (timed-prime-test n)
(newline) (display n) (start-prime-test n (current-inexact-milliseconds)))

(define (start-prime-test n start-time)
(if (prime? n) (report-prime (- (current-inexact-milliseconds) start-time)) -1))

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

(timed-prime-test 1009)
(timed-prime-test 1013)
(timed-prime-test 1019)
(timed-prime-test 10007)
(timed-prime-test 10009)
(timed-prime-test 10037)
(timed-prime-test 100003)
(timed-prime-test 100019)
(timed-prime-test 100043)
(timed-prime-test 1000003)
(timed-prime-test 1000033)
(timed-prime-test 1000037)

Exercise 1.25

巨大な数の演算をしてしまう。。。

#lang Racket
(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 (square a) (* a a))

(define (expmod2 base exp m)
(remainder (fast-expt base exp) m))

(define (fast-expt base exp)
(cond
((= exp 0) 1)
(( even? exp) (square (fast-expt base (/ exp 2))))
(else (* base (fast-expt base (- exp 1))))))

Exercise 1.26

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

これは、expmodを二回計算してしまうため、計算料の節約が帳消しになる。

 

Exercise 1.27

#lang Racket
(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 (square a) (* a a))

(define (fermat-test n a)
(= (expmod a n n) a))

(define (carmichael-prime? n times)
(cond ((= times 0) true)
((fermat-test n times) (carmichael-prime? n (- times 1)))
(else false)))

(define (carmichael-test n) (carmichael-prime? n (- n 1)))

(carmichael-test 6601)

Exercise 1.28

;(= expmod( a n-1 n) 1)
; n is prime
;任意のaについていかが成り立つ
; 0 < a < n (a∈N)
; a^(n-1) ≡ 1 (mod n)
;かつ、以下を満たすaが存在しない
; 1 < a < n-1
; a^2 ≡ 1 (mod n)

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

(define (square a) (* a a))

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

(define (fast-prime2? n times)
(cond ((= times 0) true)
((miller-rabin-test n) (fast-prime2? n (- times 1)))
(else false)))

(fast-prime2? 2821 10)
(fast-prime2? 6601 100)
(fast-prime2? 10007 100)