平方根を求めるアルゴリズムについて・・・

次の文章の平方根を求めるアルゴリズムの疑似言語での記述の仕方を教えてください。

変数名等は任意に設定して良い。またアルゴリズムは任意の正数の平方根を求められるようにすること。求める精度は１０－８とする。

（√のない計算機）
Ｔ君はある資格試験を受験しに行った。その試験では、電卓を持ち込むことができる。当然に計算問題が出題され、計算した結果、答えは√１４とでた。回答しようとしたところ、選択肢は小数で書いてある。ところが平方根を計算しようと思ったら√キーがない電卓だった。
どうしよう・・・

まず４×４＝１６であるから、とりあえず１４を４で割ってみた。

１４÷４＝３．５

言わずもがなであるが、√１４は二乗すると１４になる正の数のことである。
√１４は４と３．５の間にあることが分かる。
とりあえず、今度は１４を４と３．５のあいだの３．７５で割ってみる。

１４÷３．７５＝３．７３３３３３３３３３

ということは√１４は３．７５と３．７３３３３３３３３３のあいだにあるわけだから同じように１４を３．７４１６６６６６７で割ってみる。

１４÷３．７４１６６６６６７＝３．７４１６４８１０７

これで√１４が小数点第４位までが求められた。あとはこの作業を繰り返せば、徐々に精度は良くなるはずである。

No.3 回答者： asuncion 回答日時： 2007/09/04 21:41

> まず４×４＝１６であるから、とりあえず１４を４で割ってみた。

出発点は、実は任意の正の数でよかったりします。
繰り返す作業の回数が1～2回程度違うだけで。

No.2 回答者： inara 回答日時： 2007/09/04 21:25

数値計算の本に必ず出ている「ニュートン法による関数の解の求め方」を使えばいいと思いますが。

関数を f(x) としたとき、f(x) = 0 の解 x を求める漸化式は
　　　x[n+1] = x[n] + f( x[n] )/f'( x[n] )
です。関数 f(x) が f(x) = x^2 - a ならば、f(x) = 0 の解は √a ですから、これが開平のアルゴリズムになります。この場合
　　　 f( x[n] ) = x[n]^2 - a、 f'( x[n] ) = 2* x[n]
なので
　　　x[n+1] = x[n] + ( x[n]^2 - a )/( 2* x[n] ) = ( x[n] - a/x[n] )/2
が√a を求める漸化式となります。

初期値 x[0] = a として、上式を使って x[1]、x[2]、・・・ 、x[k-1]、x[k] と次々に求めていって、| x[k-1]、x[k] | < 1e-8 となった時点で計算を終わるようにすればいいのではないでしょうか。ちなみに、a = 14 の場合、計算結果は以下のようになり、n = 6 で計算を打ち切ればいいことになります。

x[0] = 14.00000000000000
x[1] = 7.50000000000000、x[1]-x[0] = -6.5
x[2] = 4.68333333333333、x[2]-x[1] = -2.81666666666667
x[3] = 3.83632858837485、x[3]-x[2] = -0.847004744958482
x[4] = 3.74282551356575、x[4]-x[3] = -0.0935030748090973
x[5] = 3.74165756905871、x[5]-x[4] = -0.0011679445070398
x[6] = 3.74165738677395、x[6]-x[5] = -0.0000001822847691
x[7] = 3.74165738677394、x[7]-x[6] = -0.0000000000000044

No.1 回答者： Tacosan 回答日時： 2007/09/04 18:27

個人的には「どこから 4 が出てきたのか」がわからないんですが, あなたはどこがわからないんですか?