二分探索の精度

さっき書いた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という細かい精度で値を表現できないためである。