ニュートン法について補足

sqrt（平方根）の計算 - 永字八法の続き。
ある式を繰り返し計算することで、無限に平方根への近似値が得られる式があり、これを割り出すのに使ったのがニュートン法。
数学者ではないので、ニュートン法の肝の部分はおいておいて、平方根を割り出すことに着目すると、以下のようになる。

前提

$a$ を、平方根が欲しい元の数値とする。
$X(0)$ を、本来ならばなんでもいいのだが、この場合、 $a$ と同じとする。

式

$X(n+1)=\frac{1}{2}\{X(n)+\frac{a}{X(n)}\}$
上記の式を繰り返していくことで、 $X(n)$ は無限に $\sqrt{a}$ に近似していくが、数学的に言うと無限回数繰り返さなければ平方根そのものにはならない。平方根に近づきはすれど、平方根よりも常に若干高い数値が出続ける。（ $a=X(0)>\sqrt{a}$ ならば）
ここで実学的にズルをする。計算精度に限界のあるコンピュータ言語（代表的なものはC言語のdouble型）を使うなら、ある程度計算すると端数が切り捨てられて丸まって、 $X(n)$ が平方根よりも小さい数値になってしまう。（ $X(n)$ が平方根以下になったかどうか確認するには、実際に二乗すればいい）そうやって、平方根以下になったところで計算をやめて、それを回答として採用するのである。

Perlで書いてみる。

sub sqrt {
	my $base = shift; # 引数を取得
	$base += 0; # 念のために引数を数値に変換しておく。
	$base == 0 and return 0; # 数値が0なら答えも0
	$base < 0 and return (); # 数値が負なら、回答無し。
	my $result = $base; # $resultは仮の平方根とする。
	while ( $result ** 2 > $base ) { # $resultの二乗が$baseを上回っている限り続ける。
		$result = ( $result + $base / $result ) / 2; # ニュートン法による漸化式処理
	}
	return $result; # 平方根を返す。
}

もっとも、Perlには標準でsqrt命令が実装されているので、これは車輪の再発明になるのだが。

Luaで書いてみる。

※2012-01-06追記

	function sqrt(base)
		if type(base)~="number" then return nil end -- 引数は数値オンリー
		if base==0 then return 0 end -- 数値が0なら答えも0
		if base<0 then return nil end -- 数値が負なら、回答無し。
		local result = base -- resultは仮の平方根とする。
		while result * result  > base do -- resultの二乗がbaseを上回っている限り続ける。
			result = ( result + base / result ) / 2; -- ニュートン法による漸化式処理
		end
		return result; -- 平方根を返す。
	end

Luaにも、math.sqrtがあるので車輪の再発明になるのだが。