第7回SICP勉強会

内容

• 関数の不動点の探索
  • 区間二分探索を利用する
  • 二分法 - Wikipedia
  • 関数の値が正と負である点にはさまれている区間には少なくとも１つの零点があるはずとして探索
• 関数の不動点の探索
  • を満たす点を不動点という
  • 不動点 - Wikipedia

問題

問題1.35

;; 問題1.35
;; 黄金比φが不動点であることを示した上で、fixed-point手続きで黄金比を求める

;; SICP P21では、黄金比はφ^2 = φ + 1を満たすとある。
;; 変形するとφ = 1 + 1/φとなる。
;; つまりφは変換 x |→ 1 + 1/xの不動点である。


;; 関数の不動点の探索
;; 1.3.3の例を持ってきた
(define tolerance 0.000001)

(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を用いて黄金比を求める
(fixed-point (lambda (x) (+ 1 (/ 1 x)))
             1.0)

;; gosh> 1.618033813400125 ;; SICP本文ではφ=1.6180となっているので正しいと考えられる

問題1.36

;; 問題1.36

;; 関数の不動点の探索
;; newlineとdisplayで探索過程が出力されるようにする
(define tolerance 0.000001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (display guess)
    (newline)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

;; fixed-pointを用いて黄金比を求める
(fixed-point (lambda (x) (+ 1 (/ 1 x)))
             1.0)

;; x |→ log(1000)/log(x)の不動点の探索を行い
;; x^x = 1000を求める
;; xlog(x) = log(1000) => x = log(1000)/log(x)
(fixed-point (lambda (x) (/ (log 1000) (log x)))
             2.0)

;; gosh> 2.0
;; 9.965784284662087
;; 3.004472209841214
;; 6.279195757507157
;; 3.759850702401539
;; 5.215843784925895
;; 4.182207192401397
;; 4.8277650983445906
;; 4.387593384662677
;; 4.671250085763899
;; 4.481403616895052
;; 4.6053657460929
;; 4.5230849678718865
;; 4.577114682047341
;; 4.541382480151454
;; 4.564903245230833
;; 4.549372679303342
;; 4.559606491913287
;; 4.552853875788271
;; 4.557305529748263
;; 4.554369064436181
;; 4.556305311532999
;; 4.555028263573554
;; 4.555870396702851
;; 4.555315001192079
;; 4.5556812635433275
;; 4.555439715736846
;; 4.555599009998291
;; 4.555493957531389
;; 4.555563237292884
;; 4.555517548417651
;; 4.555547679306398
;; 4.555527808516254
;; 4.555540912917957
;; 4.555532270803653
;; 4.555537970114198
;; 4.555534211524127
;; 4.555536690243655
;; 4.555535055574168
;; 4.5555361336081
;; 4.555535422664798
;; 41ステップ

;; 緩和法を使った場合
(fixed-point (lambda (x) (average x (/ (log 1000) (log x))))
             2.0)
;; gosh> 2.0
;; 5.9828921423310435
;; 4.922168721308343
;; 4.628224318195455
;; 4.568346513136242
;; 4.5577305909237005
;; 4.555909809045131
;; 4.555599411610624
;; 4.5555465521473675
;; 4.555537551999825
;; 4.555536019631145
;; 4.555535758730802
;; 12ステップ
 ;; 緩和法が収束に役だっていることが確認できた

問題1.37

;; 問題1.38
;; a. 連分数の近似、k項有限連分数近似の実装

;; 問題1.32で実装したaccumulation関数を流用できそう
(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 (conf-frac n d k)
  (define (conf-frac-combiner i bunbo)
    (/ (n i) (+ (d i) bunbo)))
  (define (conf-frac-term i) i)
  (define (conf-frac-next i) (+ i 1))
  (accumulate conf-frac-combiner (/ (n k) (d k)) conf-frac-term 1 conf-frac-next (- k 1)))

;; 黄金比φ = 1.6180であるから
;; 1/φ = 0.61804...となる

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           9)
;; gosh> 0.6181818181818182

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

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           11)
;; gosh> 0.6180555555555556

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           12)
;; gosh> 0.6180257510729613

;; 以上からkが11以上で4桁の精度の近似ができている


;; b. aを再帰的プロセスで実装したので、反復的プロセスで実装する
(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))

;; 分母部分を先に計算して、その結果を元に分数を作りながら
;; k=1の方向に戻っていくイメージ
(define (cont-frac n d k)
  (define (conf-frac-combiner bunbo i)
    (/ (n i) (+ (d i) bunbo)))
  (define (conf-frac-term i) (+ (- k i) 1))
  (define (conf-frac-next i) (+ i 1))
  (accumulate conf-frac-combiner (/ (n k) (d k)) conf-frac-term 1 conf-frac-next (- k 1)))

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           9)
;; gosh> 0.6181818181818182

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

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           11)
;; gosh> 0.6180555555555556

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           12)
;; gosh> 0.6180257510729613

;; 再帰版と同様の結果が得られることを確認した

;; そんなややこしいことしなくてもこっちで大丈夫
(define (cont-frac2 n d k)
  (define (iter i)
    (if (= i k)
        (/ (n k) (d k))
        (/ (n i) (+ (d i) (iter (+ i 1))))))
  (iter 1))

(define (cont-frac2-iter n d k)
  (define (iter i val)
    (if (= i 0)
        val
        (iter (- i 1)
              (/ (n i) (+ (d i) val)))))   (iter k 0.0))

問題1.38

;; 問題1.38

;; 再帰版のconf-fracを利用する
(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 (conf-frac n d k)
  (define (conf-frac-combiner i bunbo)
    (/ (n i) (+ (d i) bunbo)))
  (define (conf-frac-term i) i)
  (define (conf-frac-next i) (+ i 1))
  (accumulate conf-frac-combiner (/ (n k) (d k)) conf-frac-term 1 conf-frac-next (- k 1)))


(define (e-2 k)
  (define (n i) 1.0)
  (define (d i) 
    (if (= (remainder i 3) 2)
        (* 2 (+ 1 (quotient i 3)))
        1))
  (conf-frac n d k))

(define (e k)
  (+ 2 (e-2 k)))

(e 7)
;; gosh> 2.7183098591549295
(e 8)
;; gosh> 2.718279569892473
(e 9)
;; gosh> 2.718283582089552
(e 10)
;; gosh> 2.7182817182817183


;; こういうやり方もある
(define (cont-frac n d k)
  (define (iter i)
    (if (= i k)
        (/ (n k) (d k))
        (/ (n i) (+ (d i) (iter (+ i 1))))))
  (iter 1))

(define (e-2 k)
  (cont-frac (lambda (x) 1.0)
             (lambda (x)
               (if (= (remainder x 3) 2)
                   (* 2 (+ 1 (quotient x 3)))
                   1.0))             10.0))

問題1.39

;; 問題1.39

;; 再帰版のconf-fracを利用する
(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 (conf-frac n d k)
  (define (conf-frac-combiner i bunbo)
    (/ (n i) (+ (d i) bunbo)))
  (define (conf-frac-term i) i)
  (define (conf-frac-next i) (+ i 1))
  (accumulate conf-frac-combiner (/ (n k) (d k)) conf-frac-term 1 conf-frac-next (- k 1)))

(define (tan-cf x k)
  (let ((xtanx (conf-frac (lambda (i) (* -1 (* x x)))
                          (lambda (i) (- (* 2 i) 1))
                          k)))
    (* -1 (/ xtanx x))))

(use math.const)
(tan-cf (/ pi 4) 8)

;; こういうのもある
(define (tan-cf x k)
  (define (iter i)
    (cond [(> i k) 0]
          [(= i 1)
           (/ x (- 1 (iter 2)))]
          [else
           (/ (* x x)
              (- (- (* i 2) 1) (iter (+ i 1))))])))   (iter 1))

その他

勉強会でライブコーディングっぽい展開になって、その時に理解が深まった気がする！