26.1.3.7 二分法

プログラムRoot2bでは，「増加値」を次々に10分の1にしてゆきました．この"10"という数は，10進表記である"1.4142…"から決めたのですが，それ以外の意味はありません．"5"でも"100"でも，同じようにして近似値を求めることができます．何か都合のよい数はあるでしょうか．

"10分の1"にするやり方では，内側のwhileの開始前のxの値をXとするとき

X，X+d，X+2d，X+3d，…， X+9d，X+10d，

について，その2乗と"2.0"とを比較しています．しかし，1段階前では

X*X < 2.0 かつ(x+10d)*(X+10d) <=2.0

であることはわかっているので，本当に調べなければいけないのは

X+d，X+2d，…， X+9d，

の9個です．もちろんどこか途中で2乗が2.0を越したら，残りの検査は省略されます．これは増加値を10分の1にしてゆく場合でした．これを例えば5分の1にすれば，調べるべき場合数は最大4，100分の1にすれば同じく99になります．それでは2分の1にしたらどうなるでしょうか．調べるべき場合数が1，すなわちX+dだけテストすればよくなるような気がします．

2分の1法のプログラムを示します．

class Root2c {
    public static void main(String argv[ ]) {
	double e=0.000000001, d, x;
	x=1.0;
	d=0.5;
	while(d >= e/2) {
	    if((x+d)*(x+d) <= 2.0)
		x=x+d;
	    d=d/2;
	}    
	System.out.println("Square root of 2 = " + x);
    }
}

Root2c.java

このプログラムでは，X，X+d，X+2dのうちのX+dだけを検査するようになっています．それで，行き過ぎの補正を避けるために(x*xではなく)x+dを2乗して調べています．

このプログラムではwhileの繰返しを30回程度実行します．回数としてはRoot2bと大差ありませんが，内側のwhileが必要なくなった分だけプログラムが単純で，かつ高速になっています．