Page List

Search on the blog

2011年5月21日土曜日

二分探索の精度

さっき書いたGoogle Code Jam Round 1のエントリーについて。
実は、largeを通すときに気を使った。
doubleの精度は15桁程度と知っていたので、hiを大きくとり過ぎると、誤差死するのではと思った。

しかし、よく考えるとこれは違うようだ。
二分探索では、hiとloが近づいていくので、hiの初期値によらず、十分な回数ループを回せば目的の値に対して相対誤差(10^-15)で収束するはず。

実際に、以下の例でもhi = 12.345678901234502と目的の値まで収束した。
二分探索では、探索の幅が狭まるにつれて、値に対する精度もよくなっていく。
普通、ループを回せば誤差が蓄積されていくと考えてしまうが、二分探索の場合は誤差が伝搬されない(前回の計算結果より高い精度で今回の計算を実施するため)と考えてよさそうだ。

int main() {
double x = 12.3456789012345;

double hi = 1e100;
double lo = 0;

REP(i, 1000) {
double mid = (hi + lo)/2;

if (mid > x)
hi = mid;
else
lo = mid;
}

printf("%.15lf\n", hi);
return 0;
}

余談だが、二分探索のループはwhileで書かない方がいい。よくバグが潜んでしまう。例えば以下の絶対誤差を停止条件にしたソースは一生停止しない。

int main() {
double x = 1234567890123.45;

double hi = 1e100;
double lo = 0;

while (hi-lo > 1e-6) {
double mid = (hi + lo)/2;

if (mid > x)
hi = mid;
else
lo = mid;
cout << lo << ":" << hi<< endl;
}

printf("%.15lf\n", hi);
return 0;
}
これは、目的の値が非常に大きいため、コンピュータ上で、1e-6という細かい精度で値を表現できないためである。

0 件のコメント:

コメントを投稿