Geek-Side

Resource > SICP Chapter1

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

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

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