sqrtの計算

質問

ルートの値を返す関数を以下のように作ります。

double sqrt(double x){
double lower,upper,middle,y;
lower = 0.0;
upper = x;
while(1){
middle =(lower+upper)/2.0;
y=midde*middle;
if(y<0.999*x){
lower=middle;
}else if (y>1.001*x){
upper=middle;
}else{
return middle;
}
}
}

この関数に十分に大きい引数xを関数sqrtに与えたとき、while文による繰り返しは最大何回実行されるか。おおよその回数をxの式で表し、理由を述べよ。

この問題が解ける方は教えて頂きたいです。

回答No.8

kmee · ベストアンサー

計算にどれだけ時間がかかるか、というのは、計算機の分野では重要な問題です。

問題には書いてないですが、このプログラムは x>=1のときしか期待通りに動作しません。
また、xが大きすぎるとオーバーフローが発生して計算できません。
「十分に大きい」というのは、プログラムが期待通りに動作する範囲、と考えるのがよいでしょう。

x>=1の場合、0 <= √x <= x です。
平方根は単調増加しますから、二分探索が使えます。

lower<=√x<=upper
として
middle=(lower+upper)/2 ※ lowerとupperの中間
y=middle*middle
とすると、

・y=x すなわち middle=√x なら、middleが答えです(終了)

・y<x すなわち middle < √x なら
lower<=middle<√x<=upper
middle<√x<=upper
よって、新たなlower(=現在のmiddle)～upperの範囲の探索をすれば答えに近づきます。

・y>x すなわち middle > √x なら
lower<=√x<middle<=upper
lower<=√x<middle
よって、lower～新たなupper(=現在のmiddle)の範囲の探索をすれば答えに近づきます。

数学なら、無限に繰り返せば lower=middle=upper=√x になります。
ですが、コンピュータでは無限は扱えません。計算誤差もあります。
そこで、一定範囲内なら同値とみなす、という方法を取ります。
・y=x すなわち middle=√x なら、middleが答えです(終了)
→
・x-e1<=y<=x+e2 すなわち √x-E1<=middle<=√x+E2(e1,e2,E1,E2>=0)なら
y=xと見做して、middleが答えとする(終了)

このプログラムではx-e1=0.999*x, x+e2=1.001*x を使用しています。
また、upper,lowerの初期値としてx,0を使用しています。これは最初に書いたように 0 <= √x <= x であるので妥当でしょう。

ここまでがプログラムの解説です。

肝心も回数についてですが。
絶対に終了する条件、というのはわかりますか?

それは「middleが取り得る値の全てが x-e1<=y<=x+e2 になる」です。

では、middleの取り得る値の範囲はどうなるでしょう。
lower<=√x<=upperということから考えます。

最小値はupper=√x,lower=√x-(upper-lower)のときで middle=√x - (upper-lower)/2
最小値はupper=√x+(upper-lower),lower=√xのときで middle=√x + (upper-lower)/2

となれば、
√x-E1<=√x - (upper-lower)/2<=√x + (upper-lower)/2<=√x+E2
であれば、どんなmiddleになっても必ず終了条件を満すことになります。

このうち、ループ回数で変化するのは、upper-lowerです。
1回目はupper-lower=x-0=xです。
2回目は upper-lower=x-x/2 または x/2-0 = x/2 です。
3回目は 4通りありますが、いずれも upper-lower=x/4 = x/(2^2) です。

では、n回目のループではどうなるでしょう?
そこから導けるmiddleの範囲は?
それが必ず終了条件に入る場合のnとは?
これらの関係式から n=xの関数 という形に変形すれば、それが答えです。

まあ、アルゴリズムと計算量について勉強したのなら、「二分探索」という時点で、計算量はO(logN)ということが思い浮ぶはず。今回の場合はNは分割数。分割数は全体/1区間の幅。

> okboy1さん
少し落ち着いてください。
#4について。これは関数で、xは引数として宣言されています。
#6について。まったく意味がわかりません。関数内で変化するのは,upper,lower,middle,yで、xは変化しません。

お礼

理解しました。
ここまで完璧に求めていた解答をくれる方がいたことに驚きです。
本当にありがとうございました。

回答No.7

akayoroshi

#5> 一回回るごとに範囲が半分になるんだから2を底としてlog(x)でしょうかね。
さらに10回ほど繰り返すと、区間が0.001(約1/(2^10))になるでしょう。

回答No.6

okboy1

ヒント
ｘ＜2.002
2.002＞x＞2
ｘ＝2
1.998＜ｘ＜2
ｘ＜1.998

見れば見るほど、この問題に問題が結構あります。。。問題としては失格かと。。。
とりあえず回答しようとすれば
回答にlimもつかわれるような。
そして問題は回数をxの式で表しではなく、ｙをxの式で表しのほうが問題として妥当かと。。。

回答No.5

επιστημη（@episteme）

一回回るごとに範囲が半分になるんだから2を底としてlog(x)でしょうかね。

回答No.4

okboy1

ｘの値が宣言されていないからです。
もしｘの値が自分が入力できれば、ｘの値次第場合分けれ回答できますが。（こうなったらもうプログラミングのもんだいではなく、プログラミングを見せかける数学問題ですが）

補足

xの式で解答ですから、その場合分けというので合っているのかも知れないです。

場合分けの解答を教えて頂きたいです。

回答No.3

akayoroshi

十分に大きな、DOUBLE_MAXに近いような値を入れると、オーバーフローが起きて正しい値は求まりません。このときの繰り返し数を見積もるのは難しいでしょう。

補足

オーバーフローなどは考慮していないことは、問題文から分かると思います。

実際に計算機で見積もるのは難しいというのは
そもそも方法として間違っていますよね。
紙面で解くテストですし。

回答No.2

okboy1

0回です。
コンパイラする時エラーが発生しますから。
コードに問題が結構多いです。
たとえば、if(y<0.999*x)とelse if (y>1.001*x)、ｙの値が最初から特定できないので、計算機がどちかを選ぶかわかりませんよ。

補足

y=middｌe*middle;
の間違えです。

ｙの値が最初から特定できないとはどういった意味でしょうか。

回答No.1

Tacosan

試してみた?

補足

はい。
ですが法則性が良く分かりませんでした。