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);
    }
}

fileRoot2c.java

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

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