誤差の話
Latest Author ぴろず /Date 2015-04-01 17:43:03 / Views 3408整数型から浮動小数点型への変換
整数型を同じビット幅の浮動小数点型に変換すると、丸め誤差が発生することがある。例えば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; }