誤差の話

Latest Author ぴろずぴろず /Date 2015-04-01 17:43:03 / Views 3408
2 (Favした一覧ページはユーザーページから)

整数型から浮動小数点型への変換

整数型を同じビット幅の浮動小数点型に変換すると、丸め誤差が発生することがある。
例えばJavaでは、long型をdouble型にキャストすると、最大で$\pm 1024$の誤差が発生する。

sqrtを用いた平方数判定

Java
longの範囲の平方数$x$に対して、次の式は$\sqrt{x}$を正しく計算した。(Oracle JDK8で実験)
(long) Math.sqrt(x)
したがって、longの範囲の非負整数に対して、平方数判定は次のようにできる。Long.MAX_VALUEで呼び出してもオーバーフローしない。
public static boolean isSquareNumber(long x) {
	long y = (long) Math.sqrt(x);
	return y * y == x;
}
このコードで、 longからdoubleへの変換sqrtdoubleからlongへの変換 の3つで誤差が発生するが、それぞれ単調性が保証されているので、
(long) Math.sqrt(x)の値は$\lfloor \sqrt{x} \rfloor$または$\lceil \sqrt{x} \rceil$となる。
したがって、$\lfloor \sqrt{x} \rfloor$または$\lceil \sqrt{x} \rceil$を求めたい場合、(long) Math.sqrt(x)の$\pm 1$まで調べるような実装をすれば十分。
public static long sqrtFloor(long x) {
	long y = (long) Math.sqrt(x);
	return x >= y * y ? y : y - 1;
}