2007-06-28-01-嗚呼平方根! - project-enigma

2007-06-28-01-嗚呼平方根!

>> Site top >> weblog >> 月別アーカイブ >> 2007年06月のlog >> 2007-06-28-01-嗚呼平方根!

最終更新日付:2013/12/31 07:38:22


嗚呼平方根!

2007 年 06 月 28 日

a の平方根 ── すなわち √a の解を x とすると、以下の式が成り立つ(一応 a は整数ということにしておく)。

x^2 = a

で、これを移項すると、

x^2 - a = 0

では、これをこう考えてみよう。

y = x^2 - a

すると、問題を2次方程式として考えることができる。解は、y = 0 となるような x を求めることだ。

で、x が a の場合( = x1 )を起点として、2次曲線の接線が x 軸に交わる点を x2 とし、その接線が x 軸と交わる場合を...という感じで再帰的に繰り返していくと、最終的に解に収束するのだ! これをニュートン法というらしい。この様子を以下に示す。

で、何でこんな話が突然出てきたか、というと、最近妄想半分に頭の中で造っているゲームで、平方根の処理が必要になったからだ。しかし、Palm OS API には平方根を求める関数が存在しないのである。RPNToGo で N 乗根の計算をやってたじゃないかって? あれは整数解が出なければ NG、というルールだったから簡単だったのだ。しかし、今度は現実的な精度で常に解を出さなければならない。しかし API はない。ならば自分で書くしかない。しかし、浮動小数点数の平方根を算出するなんて、どうやってやったらいいの? と、途方に暮れていたのである。

そんなわけで検索してみたのだ。「 C言語 平方根」と...なになに? sqrt( ) 関数を使え? #include <math.h>? いや、それがないから困っているのでございましょう? ...とかなんとかやっていると、ニュートン法による解法を紹介しているページに行き当たった。最初は「え、これで解けるの?」と思ってしまったが、じぃぃっと眺めて考える振りをしてみると、どうやらこれでいけてしまうようだ。書いてみると、驚くほどコンパクトに ── なんと数行で ── 書けてしまったではないか! 収束判断は doubleの精度的に無理な(つまり Xn - Xn+1 がゼロと判断されてしまう)レベルを検出すればいいのである意味潔く書けた。

最初は、「開平法」をごりごりとロジックにしなきゃならんかな...と思っていたのだ。開平法というのは、手計算で平方根を求めるアレである。中学校のときに習ったはずだ。あれをロジックに書きおろすというのはちょっと考えたくない。それほど難しくはないが十分すぎるほど面倒である。しかし、このニュートン法のおかげで十分に現実的な解を得ることができた。有難い限りである。そして、楽しかった。

 

コメント

このページにコメントする

 

このページのタグ

Page tag : 開発

 

 


Copyright(C) 2005-2017 project-enigma.
Generated by CL-PREFAB.