SICPを読む(6) 1.1.7 いきなり微分。

ぐはぁ、早速数学が飛び出した。僕、数学苦手です・・・。

Newton法による平方根

まず、平方根の求め方を調べる。

ニュートン法 - Wikipedia
ニュートン法による平方根の計算
- わかりやすいスライド。

いきなり微分。でも、簡単そうなので、頑張って展開した。

$\sqrt{a}$ を求めたいとき、色々展開すると、

$x_{n+1}=\frac{1}{2}(x_n + \frac{a}{x_n})$

こうなる。

$\sqrt{2}$ の時、xに初期値を1.0、aに2を代入すると、1回目の評価は1.5,繰り返すと・・・1.4142....となるはず。

理論がわかった所で。コーディングに入る。

はじめてTeXを使った。

もしかすると、SICPは、数学+TeX+Schemeまで覚えられる本かもしれない・・・良いのか悪いのか・・・。

mimeTeX/(La)TeX math tutorial
- 英語だけどまとまってる。はてなで使うときにはこの1ページで充分対応出来そう。

コーディング

ここまで来れば、後は簡単。

(define (square x)
 (* x x))
(square 10) ; test

; 平均
(define (average x y)
 (/ (+ x y ) 2))
(average 2 4) ; test

; 予測値
(define (improve guess x)
 (average guess (/ x guess)))
(improve 1.0 2) ; test

; 近似が充分か?
(define (good-enough? guess x)
 (< (abs (- (* guess guess) x)) (/ guess 1000)))
(good-enough? 1.4142 2) ; test

; 再帰で求める
(define (sqrt-iter guess x)
 (if (good-enough? guess x)
  guess
  (sqrt-iter (improve guess x) x)))
(sqrt-iter 1.0 (* 10 10)) ; 1.41421...

(define (sqrt x)
 (sqrt-iter 1.0 x))

; test
(sqrt 9)
(sqrt (+ 100 37))
(sqrt (+ (sqrt 2) (sqrt 3)))
(square (sqrt 1000))

計算量は、5回くらいで充分な値が求まるらしい。Newton法は、早いアルゴリズムであることがわかった。

追記

少し書き直した。