計算機プログラムの構造と解釈(SICP)

• けっこう溜め込んでた。順に書いてく。
• 初めのほうはコードしか残っていない。

1.16

(define (% x y) (remainder x y))
(define (square x) (* x x))

(define (expt-0 b n)
  (if (= n 0)
      1
      (* b (expt-0 b (- n 1)))))

(define (expt-1 b n)
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                 (- counter 1)
                 (* b product))))

(define (even? n)
  (= (% n 2) 0))

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

(define (my-expt b n)
  (my-expt-iter b n 1))

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

(define (my-test x y)
  (if (= y -1) "all test are passed!"
      (if (= (expt-2 x y) (my-expt x y)) (my-test x (- y 1))
          (string-append "error" (number->string x) "-" (number->string y)))))

(my-test 5 20)

1.17

(define (double n)
  (+ n n))

(define (halve n)
  (halve-iter n 1))

(define (halve-iter n a)
  (cond ((< n a) (+ (halve (- n 1)) 0.5))
        ((= (double a) n) a)
        (else (halve-iter n (+ a 1)))))

(define (my-remainder x y)
  (cond ((= x 0) 0)
        ((< x y) x)
        (else (my-remainder (- x y) y))))

(define (even? n)
  (= (my-remainder n 2) 0))

(define (_* a b)
  (_*-iter a b 0))

(define (_*-iter a b x)
  (cond ((= 0 b) x)
        ((even? b) (_*-iter (double a) (halve b) x))
        (else (_*-iter a (- b 1) (+ x a)))))

(define (my-test x y)
  (if (= y -1) "all tests are passed!"
      (if (= (* x y) (_* x y)) (my-test x (- y 1))
          (string-append "error" (number->string x) "-" (number->string y)))))

(my-test 23 123)

1.18

;;1.17.scmの設計を反復的でつくったので1.17が答え。

1.19

;!!!! --- 正しい答えではない --- !!!!

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

(define (new-fib n)
  (new-fib-iter 1 0 0 1 n))

(define (p p q count)
  (if (= count 0)
      p
      (p q (+ p q) (- count 1))))

(define (q p q count)
  (if (= count 0)
      q
      (q q (+ p q) (- count 1))))

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



(define (my-test n)
  (if (= n -1) "all tests were passed !"
      (if (= (new-fib n) (fib n)) (my-test (- n 1))
          (string-append "error" (number->string x) "-" (number->string y)))))


;(my-test 100) -> "all test were passed !"
;(my-test 500) -> "all test were passed !"


;(display (new-fib 14))
;(newline)
;(display (fib 14))
;(newline)

;2で割り切れ続けるものしか無理
;すべての数に対して上手くいくものはわからなかった。

1.20

(define (% x y)
  (remainder x y))

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

;作用的順序
(gcd 206 40) -> (% 206 40) -> 6 ;1回
(gcd 40 6) -> (% 40 6) -> 4 ;2回 
(gcd 6 4) -> (% 6 4) -> 2 ;3回 
(gcd 4 2) -> (% 4 2) -> 0 ;4回 
(gcd 2 0) -> 2 ;終了  計4回

;正規順序
(gcd 206 40) -> ;評価なし

(gcd 40 (% 206 40))
  (if (= (% 206 40) 0)) -> ;ここで解決必要1回  計1回

(gcd (% 206 40) (% 40 (% 206 40)))
  (if (= (% 40 (% 206 40)) 0)) -> ;ここで解決必要2回  計3回

(gcd (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))
  (if (= (% (% 206 40) (% 40 (% 206 40))) 0)) -> ;ここで解決必要4回  計7回

(gcd (% (% 206 40) (% 40 (% 206 40)))
     (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))))
  (if (= (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))) 0)) -> ;ここで解決必要7回  計14回
  ;ここでif文は真となり、最後に解(a)をだすために
  (% (% 206 40) (% 40 (% 206 40))) -> ;ここで解決必要4回  計18回
  -> 2 ;終了 計18回

1.21

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

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


;> (load "1.21.scm")

;> (smallest-divisor 8)
;2
;> (smallest-divisor 5)
;5
;> (smallest-divisor 17)
;17

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

1.22

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

(define (smallest-divisor n)
  (find-divisor n 2))

(define (next n)
  (if (= n 2) 3
      (+ 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 (even? a)
  (= (remainder a 2) 0))

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

(define (runtime) (current-milliseconds))

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))
      #f))

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

(define (search-for-primes from)
  (search-for-primes-iter (if (even? from) (+ from 1) from) 0)
  (newline))

(define (search-for-primes-iter from find)
  (if (< find 3)
      (search-for-primes-iter (+ 2 from) (+ find (search-for-primes-test from)))))

(define (search-for-primes-test n)
  (if (timed-prime-test n) 1 0))

;(search-for-primes 10000000000000)

;小さいほうから三つの素数

;>(search-for-primes 1000)
;..
;1009 *** 0
;..
;1013 *** 0
;..
;1019 *** 0

;>(search-for-primes 10000)
;..
;10007 *** 0
;10009 *** 0
;..
;10037 *** 0

;>(search-for-primes 100000)
;..
;100003 *** 0
;..
;100019 *** 0
;..
;100043 *** 0

;>(search-for-primes 1000000)
;..
;1000003 *** 0
;..
;1000033 *** 0
;..
;1000037 *** 0

;時間のデータ。
;どれも0だから参考にならない。
;もっと桁を大きくしてみる。

;>(search-for-primes 1000000000000)
;..
;1000000000039 *** 1125
;..
;1000000000061 *** 1078
;1000000000063 *** 1094
;>(search-for-primes 10000000000000)
;..
;10000000000037 *** 3516
;..
;10000000000051 *** 3453
;..
;10000000000099 *** 3453

;大体、3.2倍程度となっている。
;√10は3.16程度であるため、このデータは予想を支持する。

1.23

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

(define (smallest-divisor n)
  (find-divisor n 2))

(define (next n)
  (if (= n 2) 3
      (+ 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 (even? a)
  (= (remainder a 2) 0))

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

(define (runtime) (current-milliseconds))

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))
      #f))

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

(define (search-for-primes from)
  (search-for-primes-iter (if (even? from) (+ from 1) from) 0)
  (newline))

(define (search-for-primes-iter from find)
  (if (< find 3)
      (search-for-primes-iter (+ 2 from) (+ find (search-for-primes-test from)))))

(define (search-for-primes-test n)
  (if (timed-prime-test n) 1 0))

(search-for-primes 10000)

;小さいほうから三つの素数
;同じ結果

;時間のデータ。
;どれも0だから参考にならない。
;もっと桁を大きくしてみる。

;>(search-for-primes 1000000000000)
;1000000000039 *** 625 前回 1125
;1000000000061 *** 562 前回 1078
;1000000000063 *** 563 前回 1094
;>(search-for-primes 10000000000000)
;10000000000037 *** 1922 前回 3516
;10000000000051 *** 1828 前回 3453
;10000000000099 *** 1843 前回 3453

;速くはなっているが、2倍より少し遅い。
;おそらく、if文が毎回入ることによる減速だろうと思われる。

1.24

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

(define (even? a)
  (= (remainder a 2) 0))

(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 (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

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

(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

(define (runtime) (current-milliseconds))

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
  (if (fast-prime? n 10)
      (report-prime (- (runtime) start-time))
      #f))

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

(define (search-for-primes from)
  (search-for-primes-iter (if (even? from) (+ from 1) from) 0)
  (newline))

(define (search-for-primes-iter from find)
  (if (< find 3)
      (search-for-primes-iter (+ 2 from) (+ find (search-for-primes-test from)))))

(define (search-for-primes-test n)
  (if (timed-prime-test n) 1 0))

(search-for-primes 2147483500)

;小さいほうから三つの素数
;1009 *** 0
;..
;1013 *** 0
;..
;1019 *** 0

;>(search-for-primes 10000)
;..
;10007 *** 0
;10009 *** 0
;..
;10037 *** 0

;>(search-for-primes 100000)
;..
;100003 *** 0
;..
;100019 *** 0
;..
;100043 *** 0

;>(search-for-primes 1000000)
;..
;1000003 *** 0
;..
;1000033 *** 0
;..
;1000037 *** 0

;時間のデータ。
;どれも0だから参考にならない。
;もっと桁を大きくしてみる。

;>(search-for-primes 1000000000000)
;random: expects argument of type <exact integer in [1, 2147483647]>;given 1000000000000

;>(search-for-primes 10000000000000)

;時間が計れない。

1.25

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

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

(define (even? a)
  (= (remainder a 2) 0))

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

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

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

(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

(define (runtime) (current-milliseconds))

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
  (if (fast-prime? n 10)
      (report-prime (- (runtime) start-time))
      #f))

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

(define (search-for-primes from)
  (search-for-primes-iter (if (even? from) (+ from 1) from) 0)
  (newline))

(define (search-for-primes-iter from find)
  (if (< find 3)
      (search-for-primes-iter (+ 2 from) (+ find (search-for-primes-test from)))))

(define (search-for-primes-test n)
  (if (timed-prime-test n) 1 0))

;(search-for-primes 1000000)
(display (expmod 3 4 4))
(newline)

;正しく動いているようだが、ものすごく時間がかかる。
;しかし、余剰算出計算と乗計算を分けた上記の書き方のほうが意味的には正しいように思う。

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

;この形だと、最終的に1が帰り、それにbaseを掛けた数とmとの「あまり」を算出し
;今度はその「あまり」とmとの「あまり」を算出し、
;以降はそれの繰り返しとなり、変な事態となる。

(display (expmod 3 4 4))
(newline)

;手続きを書き出してみる

(expmod 3 4 4)
(remainder (square (expmod 3 2 4)) 4)
(remainder (square (remainder (square (expmod 3 1 4)) 4)) 4)
(remainder (square (remainder (square (remainder (* 3 (expmod 3 0 4)) 4)) 4)) 4)
(remainder (square (remainder (square (remainder (* 3 1) 4)) 4)) 4)
(remainder (square (remainder (square (remainder 3 4)) 4)) 4)
(remainder (square (remainder (square 3) 4)) 4)
(remainder (square (remainder 9 4)) 4)
(remainder (square 1) 4)
(remainder 1 4)
1

;すごい。正しい答えは出ている。なんでだ？
;ステップ数は変わらずに、スペース数はむしろ増えているように思える。
;速いのはなぜかわからない。
;関数呼び出しが重いのか？
;戻ってくる過程で計算が小さい数に限られるからだろうか？
;「*」より「remainder」のほうが速いんだろうか？
;良くわからない。なぞである。

1.26

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

;良くわからない。
;むしろ逆に遅くなるように思われる。
;squareを使う場合は、(expmod base (/ exp 2) m)は一度計算するのみで十分である。
;しかし、この場合、1回呼ばれるごとに2回づつ計算しないといけなくなる。

1.27

(define (square n)
  (* n n))
(define (divides? a b)
  (= (remainder b a) 0))
(define (even? a)
  (= (remainder a 2) 0))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (next n)
  (if (= n 2) 3
      (+ 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 (prime? n)
  (= n (smallest-divisor n)))

(define (prime-test n)
  (if (prime? n)
      (void (display (string-append (number->string n) " is prime."))
            (newline))
      (void (display (string-append (number->string n) " is not prime."))
            (newline))))

(define (fermat-test-all n)
  (define (try-it a)
    (try-it-iter a))
  (define (try-it-iter a)
    (cond ((= a 0) #t)
          ((= (expmod a n n) a) (try-it-iter (- a 1)))
          (else #f)))
  (try-it (- n 1)))

(define (carmichael-test n)
  (if (fermat-test-all n)
      (void (display "but all test were passed")
            (newline))
      (void (display "and test faild.")
            (newline))))

(prime-test 561)
(carmichael-test 561)
(newline)
(prime-test 1105)
(carmichael-test 1105)
(newline)
(prime-test 1729)
(carmichael-test 1729)
(newline)
(prime-test 2465)
(carmichael-test 2465)
(newline)
(prime-test 2821)
(carmichael-test 2821)

;結果
;561 is not prime.
;but all test were passed
;
;1105 is not prime.
;but all test were passed
;
;1729 is not prime.
;but all test were passed
;
;2465 is not prime.
;but all test were passed
;
;2821 is not prime.
;but all test were passed

1.28

;題意が理解できない。いったん飛ばす。

1.29

;積分てなんだ？
;高校時代数学を全然ちゃんとやらなかったのでまったくわからない。
;でも書いてある式からとりあえず手続きには出来る。
;なんの数値を計算する手続きなんだろう？？

(define (cube x) (* x x x))

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a b)
         (sum term (next a) next b))))

(define (simpson f a b n)
  (define (h) (/ (- b a) n))
  (define (y k l)
    (* (f (+ a (* k (h))))
       (cond ((or (= 0 k) (= k l)) 1.0)
             ((= (remainder k 2) 0) 2.0)
             (else 4.0))))
  (define (next x) (+ x 1))
  (* (/ (h) 3) (sum y 0 next n)))

(simpson cube 0 1.0 100)
;-> 0.24999999999999992
;before -> 0.24998750000000042

(simpson cube 0 1.0 100)
;-> 0.2500000000000003
;before -> 0.249999875000001

;1/4が正確な値らしいので、前のアルゴリズムより正確になっている。
;なんか良くわからないがコレでいいみたい。
;ちなみにアルゴリズム中の少数指定している部分を全部整数にすると、
;-> 1/4 
;となる。Schemeは分数をそのまま計算できる。

1.30

(define (cube x) (* x x x))
(define (inc n) (+ 1 n))

;;;ここから
(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ result (term a)))))
  (iter a 0))
;;;ここまで

(sum cube 1 inc 10)

1.31

;; a-1
(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))
;再帰的プロセス

;; a-2
(define (factorial n)
  (define (inc n) (+ n 1))
  (define (term n) n)
  (product term 1 inc n))

;(factorial 6) -> 720

;; a-3
(define (pi-sum n)
  (define (square x) (* x x))
  (define (next x) (+ x 2))
  (* 4
     (/ (* 2.0 (/ (product square 4 next n) n))
     (product square 3 next n))))

;(pi-sum 120) -> 3.154709779540688
;(pi-sum 200) -> inf

;↑を書いたが分母分子それぞれの数列の掛け算を先にやっているので
;早々無限大数となり計算不能になる。

;; a-3 take2
(define (pi-sum-2 n)
  (define (term n)
    (/ (* n (+ n 2.0)) (* (+ 1.0 n) (+ 1.0 n))))
  (define (next x) (+ x 2.0))
  (* 4.0 (product term 2.0 next n)))

;↑のようにした。良く考えればコレのほうが全然きれいじゃないか。

;(pi-sum-2 200) -> 3.1493784731686008
;(pi-sum-2 10000000) -> 3.1415928106627433

;いい感じだ。

;; b
(define (product term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* result (term a)))))
  (iter a 1))

;反復的プロセス。こんな感じでいいはず。

;(pi-sum-2 200) -> 3.1493784731686008

;完了

1.32

;; a
;高階関数の高階関数か、lispはやることが凄い。楽しい。
;そういえばRailsでDRYの原則とかいうのがあったけど、これもDRYだなー。

(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
                (accumulate combiner null-value
                            term (next a) next b))))
;再帰的プロセスを生成。

(define (inc n) (+ n 1))
(define (return n) n)

;sum
(define (sum term a next b)
  (accumulate + 0 term a next b))

(define (list-sum n)
  (sum return 1 inc n))

;(list-sum 10) -> 55

;product
(define (product term a next b)
  (accumulate * 1 term a next b))

(define (factorial n)
  (product return 1 inc n))

;(factorial 6) -> 720

;; b
(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner result (term a)))))
  (iter a null-value))

;反復的プロセスを生成。

;(factorial 6) -> 720

;ok

1.33

;言ってることが微妙に良くわからないが、こういうことかな？
(define (filtered-accumulate combiner filter null-value term a next b)
  (if (> a b)
      null-value
      (combiner (if (filter a) (term a)
                    null-value)
                (filtered-accumulate combiner filter null-value
                                     term (next a) next b))))
;上記は再帰的プロセスを生成。

(define (filtered-accumulate combiner filter null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner result (if (filter a) (term a)
                                            null-value)))))
  (iter a null-value))
;上記は反復的プロセスを生成。

;; a
;sum
(define (filtered-sum term filter a next b)
  (filtered-accumulate + filter 0 term a next b))

;prime?
(define (inc n) (+ n 1))
(define (square n) (* n n))
(define (divides? a b) (= (remainder b a) 0))
(define (prime? n)
  (define (smallest-divisor n) (find-divisor n 2))
  (define (next n) (if (= n 2) 3 (+ 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)))))
  (= n (smallest-divisor n)))

;目的の手続き
(define (sum-prime-between a b)
  (filtered-sum square prime? a inc b))

;(sum-prime-between 2 20) -> 1027
;(+ (* 2 2) (* 3 3) (* 5 5) (* 7 7) (* 11 11) (* 13 13) (* 17 17) (* 19 19)) -> 1027

;; b
;product
(define (filtered-product term filter a next b)
  (filtered-accumulate * filter 1 term a next b))

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

;目的の手続き
(define (product-gcd-smaller n)
  (define (filter i) (= (gcd i n) 1))
  (define (return x) x)
  (filtered-product return filter 1 inc n))

;(product-gcd-smaller 20) -> 8729721
;(* 1 3 7 9 11 13 17 19) -> 8729721

;ok

1.34

(define (f g) (g 2))
;手続きプロセスを書き出してみる。
(f f)
(f 2)
(2 2)
;> ここでエラー
;数字は関数ではないので、エラーが出ると予想。

;実際にやってみた

;> (f f)
;procedure application: expected procedure, given: 2; arguments were: 2
;> (2 2)
;procedure application: expected procedure, given: 2; arguments were: 2

;予想通り。

1.35

(define (average a b)
  (/ (+ a b) 2.0))

(define (search f neg-point pos-point)
  (let ((midpoint (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond ((positive? test-value)
                 (search f neg-point midpoint))
                ((negative? test-value)
                 (search f midpoint pos-point))
                (else midpoint))))))

(define (close-enough? x y)
  (< (abs (- x y)) 0.001))

(define (half-interval-method f a b)
  (let ((a-value (f a))
        (b-value (f b)))
    (cond ((and (negative? a-value) (positive? b-value))
           (search f a b))
          ((and (negative? b-value) (positive? a-value))
           (search f b a))
          (else
           (error "Values are not of opposite sine" a b)))))

;(half-interval-method sin 2.0 4.0)
;(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3))
;                      1.0
;                      2.0)

(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)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

;(fixed-point cos 1.0)
;(fixed-point (lambda (y) (+ (sin y) (cos y)))
;             1.0)
(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y)))
               1.0))

;(sqrt 2)
;φ = (1+√5)/2であり
;x → 1 + 1/xの不動点であることがしめせればよいので、
;
;(1+√5)/2 = 1 + 1/((1+√5)/2)が成りたてばよい。
;...いろいろ式変換したができない。所詮文系か。
;他ので試してみる。
;
;φ~2 = φ+1でもある
;
;φ = (φ+1)/φ
;φ = 1 + 1/φ
;ここで
;x = 1 + 1/x
;なりたつ。できた!

(fixed-point (lambda (y) (+ 1 (/ 1 y))) 1.0)

;> 1.6180327868852458
;完了。

1.36

(define (average a b)
  (/ (+ a b) 2.0))

(define (search f neg-point pos-point)
  (let ((midpoint (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond ((positive? test-value)
                 (search f neg-point midpoint))
                ((negative? test-value)
                 (search f midpoint pos-point))
                (else midpoint))))))

(define (close-enough? x y)
  (< (abs (- x y)) 0.001))

(define (half-interval-method f a b)
  (let ((a-value (f a))
        (b-value (f b)))
    (cond ((and (negative? a-value) (positive? b-value))
           (search f a b))
          ((and (negative? b-value) (positive? a-value))
           (search f b a))
          (else
           (error "Values are not of opposite sine" a b)))))

;(half-interval-method sin 2.0 4.0)
;(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3))
;                      1.0
;                      2.0)

(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)))
      (display next)
      (newline)
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(fixed-point (lambda (x) (/ (log 1000) (log x))) 10)
;-> 4.555532257016376

1.37

;a.
(define (cont-frac n d k)
  (define (cont-frac-iter n d k i)
    (if (= k i)
        (/ (n i) (d i))
        (/ (n i) (+ (d i) (cont-frac-iter n d k (+ i 1))))))
  (cont-frac-iter n d k 1))
;再帰的プロセス

;(/ 1 1.6180327868852458)
;-> 0.6180344478216819

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           10)
;-> 0.6179775280898876

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           11)
;-> 0.6180555555555556
; 11回以上必要。

;b.
;反復的プロセス
(define (cont-frac n d k)
  (define (cont-frac-iter n d k i t)
    (if (= 1 i)
        (/ (n 1) t)
        (cont-frac-iter n d k (- i 1)
                        (+ (d (- i 1)) (/ (n i)
                                          (if (= k i) (d i)
                                              t))))))
  (cont-frac-iter n d k k 0))

;逆たどりでやった。

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           11)

;-> 0.6180555555555556
;ok

1.38

(define (pow x y)
  (cond ((= y 0) 1)
        ((= y 1) x)
        (else (* x (pow x (- y 1))))))

(define (cont-frac n d k)
  (define (cont-frac-iter n d k i)
    (if (= k i)
        (/ (n i) (d i))
        (/ (n i) (+ (d i) (cont-frac-iter n d k (+ i 1))))))
  (cont-frac-iter n d k 1))

(cont-frac (lambda (i) 1.0)
           (lambda (i) 
             (if (= (remainder (+ i 1) 3) 0)
                 (pow 2 (/ (+ i 1) 3))
                 1))
           1000)
                 
;> (load "1.38.scm")
;0.7182879732937529

• ここまで。
• やってみてわかったけど、この本は本当に面白い。
• まだまだ先がやりたい。