二分探索の精度

さっき書いたGoogle Code Jam Round 1のエントリーについて。

実は、largeを通すときに気を使った。

doubleの精度は15桁程度と知っていたので、hiを大きくとり過ぎると、誤差死するのではと思った。

しかし、よく考えるとこれは違うようだ。

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

実際に、以下の例でもhi = 12.345678901234502と目的の値まで収束した。

二分探索では、探索の幅が狭まるにつれて、値に対する精度もよくなっていく。

普通、ループを回せば誤差が蓄積されていくと考えてしまうが、二分探索の場合は誤差が伝搬されない（前回の計算結果より高い精度で今回の計算を実施するため）と考えてよさそうだ。

view plainprint?

1. int main() {  
2. double x = 12.3456789012345;  
3.   
4. double hi = 1e100;  
5. double lo = 0;  
6.   
7. REP(i, 1000) {  
8.     double mid = (hi + lo)/2;  
9.   
10.     if (mid > x)  
11.         hi = mid;  
12.     else  
13.         lo = mid;  
14. }  
15.   
16. printf("%.15lf\n", hi);  
17. return 0;  
18. }  

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で書かない方がいい。よくバグが潜んでしまう。例えば以下の絶対誤差を停止条件にしたソースは一生停止しない。

view plainprint?

1. int main() {  
2.     double x = 1234567890123.45;  
3.   
4.     double hi = 1e100;  
5.     double lo = 0;  
6.   
7.     while (hi-lo > 1e-6) {  
8.         double mid = (hi + lo)/2;  
9.   
10.         if (mid > x)  
11.             hi = mid;  
12.         else  
13.             lo = mid;  
14.         cout << lo << ":" << hi<< endl;  
15.     }  
16.   
17.     printf("%.15lf\n", hi);  
18.     return 0;  
19. }  

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