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なので）詳しくはこちらを参考。

Babylonian Methodの公式：

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

スクリプトで書くと

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

こう書かなかったのは前講で学んだ「High-Order Function」を理解させるための先生なりの配慮なのではないかと思っている。

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

output

>>> square_root(25)
5.0

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)と入れるとどうなるか。。。

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判定が出る。

output

>>> approx_eq(2, 2.0000000033)
False
>>> approx_eq(2, 2.000000000000000033)
True

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

解決策#1

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

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関数にも当てはめると

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回行った時点でそれを答えとして出してしまう。

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

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

>>> 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つ目に、パイソンにおける「複雑なものは小さい構成要素として分解できる（もしくは小さい構成要素こそが複雑なものを形作っている）」という道徳観に基づいた処理方法があるからこそ、これら全てが可能になっているということ。