SICP 演習問題 1.2
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)
