This article was migrated from http://rails.office.drecom.jp/takiuchi/archive/24

今週も、同僚のよしてつさんと一緒に素人くさいSICP読書会に参加してきました。

今回はサイボウズ・ラボ様のセミナールームにて開催されました。
毎度の事ながら、非常に素晴らしい環境を利用させていただいことを感謝いたします。

参加者は、だいたい20名前後だったでしょうか。前回同様、演習問題を黙々と解いていくという形式で進められました。今回の範囲は、演習問題 1.34〜1.36です。ようやく lambda で出てきたところですね。主に、関数の不動点（fixed point）の算出を行いました。

関数 f(x) の不動点とは、f(x) = x となるような x の事です。グラフを（x,y）平面にプロットして考えると、y = f(x) と y = x の交点が全て不動点になります。なので、不動点は一個であるとは限りません。不動点が存在しない f(x) もありえます。

今回使ったアルゴリズムは、初項 x_0 としてある値を設定し、続く数列を x_i = f(x_(i-1)) } で計算した時の、i → ∞ での極限を求める事で不動点に収束させるというものです。

こちらのサイトに図解入りのわかりやすい説明がありますね。

ということで、今回使ったコードを置いておきます。 ----
; 5/17 SICP#13
(define (square x) ^*1)
(define (f g)
　(g 2))
(define (average a b)
　(/ (+ a b) 2))
(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 "Value are not of opposite sign" a b)))))
(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))
;(define (sqrt x)
;　(fixed-point (lambda (y) (/ x y)) 1.0))
(define (sqrt x)
　(fixed-point (lambda (y) (average y (/ x y))) 1.0))
; ex 1.35
(define phi
　(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0))
; ex 1.36
(define (fixed-point-v f first-guess)
　(define (close-enough? v1 v2)
　　(< (abs (- v1 v2)) tolerance))
　(define (try guess step-count)
　　(let ((next (f guess)))
　　　(display step-count)
　　　(display "\t")
　　　(display guess)
　　　(newline)
　　　(if (close-enough? guess next)
　　　　　next
　　　　　(try next (inc step-count)))))
　(try first-guess 1))

This article was migrated from http://rails.office.drecom.jp/takiuchi/archive/24

1. 1 x x