2 (Favした一覧ページはユーザーページから) Tweet

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

整数型を同じビット幅の浮動小数点型に変換すると、丸め誤差が発生することがある。
例えば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への変換・ sqrt・ doubleから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;
}