Exersise 1.8
Fermat's Little Theorem
baseをexp乗してmで割った余りを求める。
(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))))
aのn乗をnで割った時の余りと、aのn/2乗をnで割った時の余りを2乗し、nで割った時の余りは等しい。
aのn乗をnで割った時の余りと、aの(n-1)乗をnで割った時の余りa倍し、nで割った時の余りは等しい。
TODO Exercise 1.28
わからない。。。。解法(素人くさいSICP「独」書会)
http://sicp.naochan.com/memo.pl?p=%CC%E4%C2%EA1.28
ミラー-ラビン素数判定法(Wikipedia)
http://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC-%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95
ミラー・ラビン(Miller-Rabin)テストの説明
http://www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/miller.html
Exercise 1.29
(define (simpson-integral f a b n)
(let ((h (/ (- b a) n)))
(define (simpson-iter k)
(cond [(<= n k) (f b)]
[(even? k) (+ (* 2 (f (+ a (* k h)))) (simpson-iter (+ k 1)))]
[else (+ (* 4(f (+ a (* k h)))) (simpson-iter (+ k 1)))]))
(* (/ h 3) (+ (f a) (simpson-iter 1)))))
(simpson-integral cube 0 1 1000)
Exercise 1.30
(define (sum term a next b)
(define (iter a result)
(if (> a b) result
(iter (next a) (+ result (term a)))))
(iter (next a) (term a)))
(use gauche.test)
(test-start "sum")
(test* "1のsum" 1 (sum (lambda (a) a) 1 (lambda (a) (+ a 1)) 1))
(test* "10のsum" 55 (sum (lambda (a) a) 1 (lambda (a) (+ a 1)) 10))
(test-end)
Exersise 1.31 a
(define (product term a next b)
(define (iter a)
(if (> a b) 1
(* (term a) (iter (next a)))))
(* (term a) (iter a)))
(use gauche.test)
(test-start "product")
(test* "1の階乗" 1 (product (lambda (a) a) 1 (lambda (a) (+ a 1)) 1))
(test* "3の階乗" 6 (product (lambda (a) a) 1 (lambda (a) (+ a 1)) 3))
(test-end)
(define (pai n)
(define (next a) (+ 1 a))
(* 4 (/ (product (lambda (n) (cond [(= n 1) 2] [(even? n) (+ n 2)] [else (+ n 1)])) 1 next n)
(product (lambda (n) (if (even? n) (+ n 1) (+ n 2))) 1 next n))))
(exact->inexact (pai 100000))
Exersise 1.31 b
(define (product term a next b)
(define (iter a result)
(if (> a b) result
(iter (next a) (* result (term a)))))
(iter (next a) (term a)))
(use gauche.test)
(test-start "product")
(test* "1の階乗" 1 (product (lambda (a) a) 1 (lambda (a) (+ a 1)) 1))
(test* "3の階乗" 6 (product (lambda (a) a) 1 (lambda (a) (+ a 1)) 3))
(test-end)
Exersise 1.32 a
(define (accumulate combiner null-value term a next b)
(define (iter a result)
(if (> a b) result
(iter (next a) (combiner (term a) result))))
(iter a null-value))
(use gauche.test)
(test-start "accumulate")
(test* "1の階乗" 1 (accumulate * 1 (lambda (a) a) 1 (lambda (a) (+ a 1)) 1))
(test* "3の階乗" 6 (accumulate * 1 (lambda (a) a) 1 (lambda (a) (+ a 1)) 3))
(test* "1のsum" 1 (accumulate + 0 (lambda (a) a) 1 (lambda (a) (+ a 1)) 1))
(test* "10のsum" 55 (accumulate + 0 (lambda (a) a) 1 (lambda (a) (+ a 1)) 10))
(test-end)
Exersise 1.32 b
(define (accumulate combiner null-value term a next b)
(define (iter a)
(if (> a b) null-value
(combiner (term a) (iter (next a)))))
(iter a))
(use gauche.test)
(test-start "product")
(test* "1の階乗" 1 (accumulate * 1 (lambda (a) a) 1 (lambda (a) (+ a 1)) 1))
(test* "3の階乗" 6 (accumulate * 1 (lambda (a) a) 1 (lambda (a) (+ a 1)) 3))
(test* "1のsum" 1 (accumulate + 0 (lambda (a) a) 1 (lambda (a) (+ a 1)) 1))
(test* "10のsum" 55 (accumulate + 0 (lambda (a) a) 1 (lambda (a) (+ a 1)) 10))
(test-end)
Exersise 1.3.3 a
(define (filtered-accumulate combiner null-value term a next b filter)
(define (iter a)
(cond [(> a b) null-value]
[(filter a) (combiner (term a) (iter (next a)))]
[else (iter (next a))]))
(iter a))
(use gauche.test)
(test-start "素数の2乗の和")
(test* "1まで" 1 (filtered-accumulate + 0 (lambda (a) (* a a)) 1 (lambda (a) (+ a 1)) 1 prime?))
(test* "5まで" 39 (filtered-accumulate + 0 (lambda (a) (* a a)) 1 (lambda (a) (+ a 1)) 5 prime?))
(test-end)
Exersise 1.3.3 b
(define prime-to?
(lambda (n)
(lambda (i)
(if (= (gcd i n) 1)
#t #f))))
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
(use gauche.test)
(test-start "n > iで gcd(i n) が 1 のものの積")
(test* "1まで" 1 (filtered-accumulate * 1 (lambda (a) a) 1 (lambda (a) (+ a 1)) 1 (prime-to? 1)))
(test* "5まで" (* 1 2 3 4) (filtered-accumulate * 1 (lambda (a) a) 1 (lambda (a) (+ a 1)) 5 (prime-to? 5)))
(test* "10まで" (* 1 3 7 9) (filtered-accumulate * 1 (lambda (a) a) 1 (lambda (a) (+ a 1)) 10 (prime-to? 10)))
(test-end)
Exersise 1.3.4
(define (f g) (g 2)) (f f)(f f)
-> (f 2)
-> (2 2)
(2 2)を評価するとエラーになる。
Exersise 1.35
(exact->inexact (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1))
Exersise 1.36
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(newline)
(display next)
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
(fixed-point cos 1.0)
Exersise 1.37
;; 再帰バージョン
(define (cont-frac n d k)
(define (iter i)
(if (= i k)
(/ (n i) (d i))
(/ (n i) (+ (d i) (iter (+ i 1))))))
(iter 1))
;; 反復バージョン
(define (cont-frac n d k)
(define (iter i result)
(if (= i 0)
result
(iter (- i 1)
(/ (n i) (+ (d i) result)))))
(iter k 0))
;; 小数点第4位の精度
(define (cont-frac-torelance)
(define (cont-frac-golden k)
(cont-frac (lambda (i) 1.0) (lambda (i) 1.0) k))
(define (cont-frac-accurate i)
(if (= (round (* 10000 (cont-frac-golden (+ i 1)))) (round (* 10000 (cont-frac-golden i))))
i
(cont-frac-accurate (+ i 1))))
(cont-frac-accurate 1))
(cont-frac-torelance)
Exersise 1.38
cont-fracを再掲
;; 再帰バージョン
(define (cont-frac n d k)
(define (iter i)
(if (= i k)
(/ (n i) (d i))
(/ (n i) (+ (d i) (iter (+ i 1))))))
(iter 1))
(exact->inexact (cont-frac (lambda (i) 1) (lambda (i) (let ((tmp (+ i 1))) (if (= (remainder tmp 3) 0) (* (quotient tmp 3) 2) 1))) k))
Exersise 1.39
(define (tan-cf x k)
(exact->inexact
(cont-frac
(lambda (i) (if (= 1 i) x (* x x -1)))
(lambda (i) (- (* 2 i) 1)) 1000)))
(tan-cf 3.14 1000)
Exersise 1.40
(define (cubic a b c) (lambda (x) (+ (* x x x) (* a x x) (* b x) c)))
Exersise 1.41
(define (inc value)
(+ value 1))
(define (double func)
(lambda (x)
(func (func x))))
; テスト
(use gauche.test)
(test-start "doubleのテスト")
(test* "0の場合" 2 ((double inc) 0))
(test* "10の場合" 12 ((double inc) 10))
(test-end)
(((double (double double)) inc) 5)
Exersise 1.42
(define (compose f g) (lambda (x) (f (g x)))) (define (square x) (* x x)) ; テスト (use gauche.test) (test-start "Exercise 1.42") (test* "問題通りになっているか？" 49 ((compose square inc) 6)) (test-end)
Exersise 1.43
(define (repeated func n)
(define (iter repeated-func i)
(if (= 1 i)
repeated-func
(iter (compose repeated-func func) (- i 1))))
(iter func n))
(define (square x)
(* x x))
; テスト
(use gauche.test)
(test-start "Exersise 1.43")
(test* "問題通りになっているか？" 625 ((repeated square 2) 5))
(test-end)
Exersise 1.44
(define dx 0.00001) (define (smooth func) (lambda (x) (/ (+ (func (- x dx)) (func x) (func (+ x dx))) 3))) (define (n-fold-smooth func repeat) ((repeated smooth repeat) func))
gosh> ((n-fold-smooth square 5) 10) 100.00000000033333
Exersise 1.45
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(newline)
(display next)
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
(define (average-damp f)
(lambda (x) (average x (f x))))
(define (average n m)
(/ (+ n m) 2))
(define (nth-root x n)
(fixed-point ((repeated average-damp (- n 1)) (lambda (y) (/ x (expt y n))))
1.0))
(use gauche.test) (define (neary-equal? a b) (< (abs (- a b)) 1.0e-4)) (test-start "Exersise 1.45") (test* "3の5乗は243" 3 (nth-root 243 4) neary-equal?) (test* "2の8乗は256" 2 (nth-root 256 7) neary-equal?) (test-end)
Exersise 1.46
(define (iterative-improve good-enough improve)
(lambda (guess)
(define (iter x)
(if (good-enough x)
x
(iter (improve x))))
(iter guess)))
(define (sqrt-iter x)
(iterative-improve
(lambda (guess)
(< (abs (- (square guess) x)) 0.001))
(lambda (guess)
(average guess (/ x guess)))))
((sqrt-iter 4) 1.0)
((sqrt-iter 81) 1.0)
(define (fixed-point f first-guess)
((iterative-improve
(lambda (guess)
(< (abs (- guess (f guess))) tolerance))
f) first-guess))
(fixed-point (lambda (y) (average y (/ 2 y))) 1.0)
(fixed-point cos 1.0)
