SICP 1.1.7 Example: Square Roots by Newton's Method

ニュートン法による開平。あるいは開根。

Procedures must be effective.

effectiveの訳は難しいが、実行可能とか具体的に答えを求める事が出来るとか言った感じか。
『yは２乗するとrになる数。』と明言しても、具体的にyは求められない。

The contrast between function and procedure is a reflection of the general distinction between describing properties of things and describing how to do things,

『性質』を表現しているだけなのと、『求め型の手順』の違い。

the distinction between declarative knowledge and imperative knowledge

『宣言的な情報』と『命令的な情報』の違い。

xの平方根を求める。最初の値候補をy1として、y2をy1とx/y1の平均とすると、y1よりy2の方がxの平方根に近付く。

ニュートン法のおさらい。
方程式 $f(x)=0$ を解く事を考える。これは $y=f(x)$ のx切片を求め事と同じ。
曲線 $y=f(x)$ 上の点 $(x_n, y_n)$ を通り傾き $f'(x_n)$ の直線は
$y - y_n = f'(x_n) (x - x_n)$
で表せる。
点 $(x_n, y_n)$ は求めるx切片にそれなりに近いとして*1この直線のx切片を $x_{n+1}$ とする時、 $x_{n+1}$ は $x_n$ よりも $y=f(x)$ のx切片に近い。
なのでこの方法を繰り返し用いる事で、目的のxを近似的に求める事が出来る。

直線 $y - y_n = f'(x_n) (x - x_n)$ 上のx切片を $(x_{n+1}, 0)$ とすると
$- y_n = f'(x_n) (x_{n+1} - x_n)$
$x_{n+1} - x_n = - \frac{y_n}{f'(x_n)}$
$x_{n+1} = x_n - \frac{y_n}{f'(x_n)}$
$y_n$ は $f(x_n)$ の事なので
$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$
で $x_{n+1}$ が求められる事になる。

rの平方根を求めるとき、
$x^2 = r$
の $x$ を求める事になる。この場合 $x^2 - r = 0$ なので、 $f(x) = x^2 - r$ として $f(x) = 0$ となる $x$ を求める。
$f'(x) = 2x$
なので
$x_{n+1} = x_n - \frac{{x_n}^2 - r}{2x_n}$
$=\frac{2{x_n}^2 - {x_n}^2 + r}{2x_n}$
$=\frac{{x_n}^2 + r}{2x_n}$
$=\frac{x_n + \frac{r}{x_n}}{2}$
となる。
本文ではxの平方根を求めるのに、最初の予想値をyとしているので、 $r$ → $x$ 、 $x_n$ → $y$ と読み替えると、
$=\frac{y + \frac{x}{y}}{2}$
確かに、新しいyを求めるのに $y$ と $\frac{x}{y}$ の平均を計算している。

DrRacketではsqrtは予め定義されていて、再定義は許されない様なので、ここではsquare-rootと言う関数として定義する。

> (square-root 9)
3.00009155413138
> (square-root (+ 100 37))
11.704699917758145
> (square-root (+ (square-root 2) (square-root 3)))
1.7739279023207892
> (square (square-root 1000))
1000.000369924366
>

ループする構文を使わずに関数を呼び出す構文のみ（ここでは再帰呼び出し）で実現出来る。

Exercise 1.6

Alyssa P. Hackerは何故ifがspecial formでなければならないのか理解出来ないので、友達のEva Lu Atorがcondを使って関数で実装してみた。Evaの単純なデモはうまく動いたのでAlyssaが開平プログラムに使ってみた。どうなるか？

new-ifは関数なので呼び出される前に全ての引数が評価されてしまう。即ちgood-enough?の結果に関わらずsqrt-iterを再帰呼び出ししてしまい、その呼び出し先でまたgood-enough?の結果に関わらずsqrt-iterを再帰呼び出ししてしまうので、無限に再帰呼び出しをしてしまい処理が完了しない。

Exercise 1.7

2乗してみて元の数との差が0.001未満、と言う事は例えば元の数が0.001未満の場合は判定には全く使えない。

> (square-root 1e-50)
0.03125
> (sqrt 1e-50)
1e-25
>

一方、元の数が非常に大きい場合は必要以上の精度を求めている。

> (square-root 100000000000)
316227.7660168379
> (sqrt 100000000000)
316227.7660168379
> (square-root 1e50)
. . user break
>

数が大きすぎると返って来ない。

good-enough?の別の実装としてguessの変化量（変化率）に基づく判断を実装してみよ。

guessが前のguessに対して0.1%未満の変化になった時に計算をやめるとすると：（かなり大きな誤差だが）

小さな数に対してそこそのこ精度を出して、大きな数字も適当な所で答えを出してくれる事が分かる。

> (square-root 0.00001)
0.03135649010771716
> (square-root2 0.00001)
0.0031622776602038957
> (sqrt 0.00001)
0.0031622776601683794
> (square-root 1.0e50)
. . user break
> (square-root2 1.0e50)
1.0000003807575104e+25
>

Exercise 1.8

立方根を求めるプログラム。
Xの立方根を求めるには、
$x^3=X$
$f(x) = x^3 - X$
の時
$f(x)=0$
となるxを求める。
$f(x) = x^3 - X$
なので
$f'(x) = 3x^2$
x切片（y=0の時）
$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$
$= x_n - \frac{{x_n}^3 - X}{3{x_n}^2}$
$= \frac{3{x_n}^3-{x_n}^3+X}{3{x_n}^2}$
$= \frac{2{x_n}^3+X}{3{x_n}^2}$
$=\frac{2x_n + \frac{X}{{x_n}^2}}{3}$
と変形出来る。問題に提示されている式のxが $X$ 、yが $x_n$ 。

good-enough?はexercise 1.7で作ったgood-enough?2を使用する。

実行結果：

> (cube-root 729.0)
9.000000000053902
> (cube-root 27.0)
3.0000005410641766
> (cube-root 0.0001)
0.04641588857275245
> (cube-root 0.001)
0.10000000198565878
>

*1:ここでは条件は詳しく述べないけど

プログラミング再入門

プログラミングをもう一度ちゃんと勉強する読書ノート

SICP 1.1.7 Example: Square Roots by Newton's Method

Exercise 1.6

Exercise 1.7

Exercise 1.8