python3でBabylonian Methodを使った関数を作る

#Babylonian Methodとは
「a function that takes an argument `x` and repeatedly refine a guess x about the square root of a parameter `a`」という処理をしてくれます。例えば`25`という数字を入れたら`5`と返してくれます。（5の2乗は25なので）詳しくは<a href="http://composingprograms.com/pages/16-higher-order-functions.html#functions-as-general-methods" target="_blank">こちら</a>を参考。

##Babylonian Methodの公式：

```math
x = \frac{x+\frac{a}{x}}{2}
```

###スクリプトで書くと

```lang:babylonian.py
def square_root(a):
	x = 1
	while x*x != a:
		x = square_root_update(x, a)
	return x

def square_root_update(x, a):
	return (x + a/x) / 2

```

###ちなみに

```
def square_root(a):
     x = 1
     while x * x != a:
         x = (x + a/x)/2
     return x
```
こう書かなかったのは前講で学んだ<a href="http://qiita.com/weedslayer/items/c8d59b0a08673f8b50fe" target="_blank">「High-Order Function」</a>を理解させるための先生なりの配慮なのではないかと思っている。

###実際に何が起きているのか

```lang:output
>>> square_root(25)
5.0
```

```lang:determination_process
1
13.0
7.461538461538462
5.406026962727994
5.015247601944898
5.000023178253949
5.000000000053722
5.0
```

`25`を入れると`square_root_update`がbabylonian methodを実行し得た数値を変数`x`の中に入れる。その後`square_root`関数が`x*x != a`かどうか確かめてくれる。そうであればそのまま出力しそうでなければ`square_root_update`を呼び出してもう一度処理を行う。その数値が`x*x = a`になるまで以上の処理を行い続ける。

##課題#1：
割り切れない数を入力するとずっとアイドリング状態に陥ってしまう。ただ例えばここに`square_root(2)`と入れるとどうなるか。。。

```lang:output
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095...
```
`1.999999999999`と永遠に答えを探し続けてしまう。。。
そこで・・・何とか解決策を。

###ちょっと復習
ところでさっき書いたコードをもう少し一般化させて考えてみる。

```
def improve(update, close, guess=1):
	while not close(guess):
		guess = update(guess)
	return guess
```

まさに先程書いたコードの一般化ですが、
1. 変数`guess`、期待値`close`関数と変数`guess`を更新し続けてくれる`update`関数があり、
2. `not close`の限り`update`関数が探し続け`guess`として返してくれる

ただこれだけだと具体的に「`guess`と`close`の数値同士がどれだけ近ければ近いとみなせるのか」分からない。

###そこで解決策
新たにその「近さを」具体的に定義してくれる関数を作る。

>
_by saying that numbers are basically equal or approximately equal as long as their difference is within some small tolerance._

その_small tolerance_がここで言う`1*10^-15`。変換の仕方が正しければ`0.00000000000000015`だったと思います。

```
def approx_eq(x, y, tolerance=1e-15):
	return abs(x-y) < tolerance
```

極僅かな差を作って変数値`guess`と`close`の差が`0.00000000000000015`以下なら`True`判定が出る。

```lang:output
>>> approx_eq(2, 2.0000000033)
False
>>> approx_eq(2, 2.000000000000000033)
True
```

つまり0が一定以上増えたらもう全部`True`で返しちゃおうってことです。

##解決策#1
道具が揃ったので`approx_eq`関数を実際に埋め込んでいきます。

```lang:babylonian.py
def square_root_update(x, a):
	return (x + a/x) / 2

def improve(update, close, guess=1):
	while not close(guess):
		guess = update(guess)
	return guess

def approx_eq(x, y, tolerance=1e-15):
	# general notion of satisfaction
	return abs(x-y) < tolerance

def square_root(a): 
	def update(x): 
		return square_root_update(x, a)
	def close(x):
		return approx_eq(x*x, a) 
	return improve(update, close)
```
`update`関数（=`square_root_update(x, a)`）と`close`関数（=`approx_eq(x*x, a)`）を`square_root`関数の中に入れておくことによってその関数のローカル領域において変数を取り扱うことが出来る。つまり新たに変数を定義する必要がなく省エネ。
`improve`関数は連続的な改良を自動化したプログラムに過ぎない。`update`と`close`によって実際の問題の処理が行われる。

###`cube_root`関数にも当てはめると

```lang:babylonian.py
def square_root_update(x, a):
	return (x + a/x) / 2

def cube_root_update(x, a):
	return (2*x + a/(x*x)) / 3

def improve(update, close, guess=1):
	while not close(guess):
		guess = update(guess)
	return guess

def approx_eq(x, y, tolerance=1e-15):
	# general notion of satisfaction
	return abs(x-y) < tolerance

def square_root(a): 
	def update(x): 
		return square_root_update(x, a)
	def close(x):
		return approx_eq(x*x, a) 
	return improve(update, close)

def cube_root(a):
	return improve(lambda x: cube_root_update(x, a),
		           lambda x: approx_eq(x*x*x, a))
```

##課題#2

`>>>cube_root(10)`とやると永遠に動き続けてしまいにはエラーを吐いてしまう。

##解決策#2
いくつか解決策がある。

###数字の誤差（=tolerance）の幅をゆるくする
具体的には`tolerance=1e-15`を`1e-14`とかにすると基準がゆるくなってエラーを吐かなくなる。

###`update`関数の更新回数を制限する
`update`関数（=`cube_root_update`関数）の試行回数を100回までし、100回行った時点でそれを答えとして出してしまう。

```lang:babylonian.py
def improve(update, close, guess=1, max_update=100):
	k = 0
	while not close(guess) and k < max_update:
		guess = update(guess)
		k += 1
	return guess
```

ちゃんと表示してくれます。

```output
>>> cube_root(10)
2.154434690031884
>>> cube_root(100)
4.641588833612778
```

役割を細かく分けてその役割ごとに関数を定義していくことによって後々問題が生じてもちょっとした変更を加えるだけで柔軟に対応できるので`Higher-Order Function`素晴らしい。

##欠点
ただ素晴らしいことだらけって言う訳でもないそうです。その一つとして取り上げられていたのがグローバルフレームがあらゆる関数名で埋まってしまうということ。そしてその関数名一つ一つが違う名前でなくてはならない。もう一つの欠点は関数同士によっては何らかの制限がかかってしまうということ。例えば`update`関数と`improve`関数同士では`argument`一つしか取れないと決まってしまうなど。

#まとめ

>
_This example illustrates two related big ideas in computer science. First, naming and functions allow us to abstract away a vast amount of complexity. While each function definition has been trivial, the computational process set in motion by our evaluation procedure is quite intricate. Second, it is only by virtue of the fact that we have an extremely general evaluation procedure for the Python language that small components can be composed into complex processes. Understanding the procedure of interpreting programs allows us to validate and inspect the process we have created._
_この例はコンピューターサイエンスにおける2つの大きな考え方に光を照らしてくれた。1つ目は名前付けと関数を使うことによって「膨大な量の複雑さ」を抽象化して片付けることができる、ということ。（例の中では）それぞれの関数の役割は正直大したことをしなかったが、実際に行われた処理はしっかりとした仕組みがあるものだった。2つ目に、パイソンにおける「複雑なものは小さい構成要素として分解できる（もしくは小さい構成要素こそが複雑なものを形作っている）」という道徳観に基づいた処理方法があるからこそ、これら全てが可能になっているということ。_