平方根

会社のプログラム見ていたら、平方根を求める関数があったので、
Pythonで書いてみました。

def sqrt(var):
	if var <= 0:
		return 0
	
	Xn_1 = var      # 漸化式の和
	Xn   = Xn_1 + 1 # 漸化式の和の１つ前
	while Xn_1 < Xn:
		Xn = Xn_1
		Xn_1 = (Xn + (var / Xn)) / 2.0 # ニュートン法
	return Xn

ただ、携帯では実数演算はつらいので、実際のプログラムは、

Xn_1 = (Xn + (var / Xn)) >> 1

となっていましたがー。
　
　
kenmoは最近、関数プログラムに興味があるので、
無理矢理、lambda式を使ってみました。

def sqrt(var):
	if var <= 0:
		return 0
	
	newton = lambda a, x: (x + (a / x)) / 2.0 # ニュートン法の無名関数
	
	Xn_1 = var
	Xn   = Xn_1 + 1
	while Xn_1 < Xn:
		Xn = Xn_1
		Xn_1 = newton(var, Xn)
	return Xn

まあ、マクロを入れただけですね、、。
　
でも、ちょっとだけコードが読みやすくなった気がします。
　
　
ただ、これでは関数プログラムとは言えないなー
なんかいい方法ないかなー。
　
と、ネットを検索していたら、
http://sky.zero.ad.jp/~zaa54437/programming/ruby/part2.htm
これを発見して、
「再帰でループを排除する」
「変数を排除する」
ということを知り、再帰に書き換えました。

def sqrt(var, n=9999):
	newton = lambda a, x: (x + (a / x)) / 2.0

	if var <= 0:
		return 0
	elif newton(var, n) >= n:
		return n
	else:
		return sqrt(var, newton(var, n))

ただ、第二引数が9999なのと、newton式を２回演算しているのが、イマイチですね（´Д｀；
　
　
だいぶ、プログラムが宣言的になった気がしなくもないですが…、

def newton(a, x):
	return (x + (a / x)) / 2.0
def sqrt(var, n):
	if var <= 0:
		return 0
	elif newton(var, n) >= n:
		return n                         # 基本条件
	else:
		return sqrt(var, newton(var, n)) # 再帰ステップ

呼び出し方法

>>>print sqrt(2, 2)
>>>1.41421356237

…うーん、かっこ悪い、、。
まー、とりあえず、これがkenmoの限界です、、。
　
　

追記

reduceを使えば、2行で書けることが判明しました…！
　
reduceっていうのは、
第一引数に関数オブジェクト、
第二引数に引数のリストを受け取る
という関数で、
渡された関数に引数のリストをガシガシ詰め込んで、累積した結果を返すものです。

def sqrt(a, cnt=5):
	return reduce(lambda x, a: (x + (a / x)) / 2.0, [a]*cnt)

第二引数は、演算回数です。
これを増やすほど、誤差が小さくなります。
　
実行結果

>>>print sqrt(5)
>>>2.23606889564

すげー！Pythonすげーよー