整数の平方根がJavaの整数であるかどうかを判別する

1. 概要

完全な正方形は、2つの等しい整数の積として表現できる数です。

この記事では、Javaで整数が完全な正方形であるかどうかを判断する複数の方法を発見します。また、各手法の長所と短所を説明して、その効率と最速を決定します。

2. 整数が完全な平方であるかどうかの確認

ご存知のように、Javaは整数を定義するための2つのデータ型を提供します。 1つは32ビットで数値を表すintで、もう1つは64ビットで数値を表すlongです。この記事では、 long データ型を使用して、最悪の場合（可能な最大の整数）を処理します。

Javaは長い数値を64ビットで表すため、長い数値の範囲は〜9,223,372,036,854,775,808から9、223,372,036,854,775,807です。また、完全数を処理しているため、正の整数のセットの処理のみに関心があります。整数をそれ自体で乗算すると、常に正の数が生成されるためです。

さらに、最大数は約2 ⁶³であるため、2 ⁶³未満の2乗の整数が約2^31.5あることを意味します。また、これらの数値のルックアップテーブルを持つことは非効率的であると考えることができます。

2.1. Javaでsqrtメソッドを使用する

整数が完全な平方であるかどうかを確認する最も簡単で簡単な方法は、sqrt関数を使用することです。ご存知のように、sqrt関数はdouble値を返します。したがって、必要なのは、結果を int にキャストし、それ自体を乗算することです。次に、結果が最初の整数と等しいかどうかを確認します。

public static boolean isPerfectSquareByUsingSqrt(long n) {
    if (n <= 0) {
        return false;
    }
    double squareRoot = Math.sqrt(n);
    long tst = (long)(squareRoot + 0.5);
    return tst*tst == n;
}

double 値を処理するときに発生する可能性のある精度エラーのために、結果に0.5を追加する必要がある場合があることに注意してください。 double 変数に割り当てられた場合、整数は小数点で表されることがあります。

たとえば、数値3を double 変数に割り当てると、その値は3.00000001または2.99999999になる可能性があります。したがって、この表現を回避するために、 long にキャストする前に0.5を追加して、実際の値を取得していることを確認します。

さらに、 sqrt 関数を1つの数値でテストすると、実行時間が速いことがわかります。一方、 sqrt 関数を何度も呼び出す必要があり、 sqrt 関数によって実行される操作の数を減らそうとすると、この種のマイクロ最適化は可能になります。実際に違いを生みます。

2.2. 二分探索の使用

二分探索を使用すると、sqrt関数を使用せずに数値の平方根を見つけることができます。

数値の範囲は1〜2 ⁶³であるため、ルートは1〜2 ^31.5です。したがって、二分探索アルゴリズムは、平方根を取得するために約16回の反復が必要です。

public boolean isPerfectSquareByUsingBinarySearch(long low, long high, long number) {
    long check = (low + high) / 2L;
    if (high < low) {
        return false;
    }
    if (number == check * check) {
        return true;
    }
    else if (number < check * check) {
        high = check - 1L;
        return isPerfectSquareByUsingBinarySearch(low, high, number);
    }
    else {
        low = check + 1L;
        return isPerfectSquareByUsingBinarySearch(low, high, number);
    }
}

2.3. 二分探索の機能強化

二分探索を強化するために、基本数の桁数を決定すると、ルートの範囲が得られることがわかります。

たとえば、数値が1桁のみで構成されている場合、平方根の範囲は1〜4です。その理由は、1桁の最大整数が9で、そのルートが3であるためです。また、数値が2桁の場合、範囲は4〜10などになります。

したがって、ルックアップテーブルを作成して、で始まる数値の桁数に基づいて平方根の範囲を指定できます。これにより、二分探索の範囲が狭くなります。したがって、平方根を取得するために必要な反復回数は少なくなります。

public class BinarySearchRange {
    private long low;
    private long high;

    // standard constructor and getters
}

private void initiateOptimizedBinarySearchLookupTable() {
    lookupTable.add(new BinarySearchRange());
    lookupTable.add(new BinarySearchRange(1L, 4L));
    lookupTable.add(new BinarySearchRange(3L, 10L));
    for (int i = 3; i < 20; i++) {
        lookupTable.add(
          new BinarySearchRange(
            lookupTable.get(i - 2).low * 10,
            lookupTable.get(i - 2).high * 10));
    }
}

public boolean isPerfectSquareByUsingOptimizedBinarySearch(long number) {
    int numberOfDigits = Long.toString(number).length();
    return isPerfectSquareByUsingBinarySearch(
      lookupTable.get(numberOfDigits).low,
      lookupTable.get(numberOfDigits).high,
     number);
}

2.4. 整数演算を使用したニュートン法

一般に、ニュートン法を使用して、整数でない場合でも、任意の数の平方根を取得できます。ニュートン法の基本的な考え方は、数を仮定することですバツ数値の平方根です N 。その後、ループを開始してルートの計算を続けることができます。これにより、Nの正しい平方根に確実に移動します。

ただし、ニュートン法にいくつかの変更を加えると、整数が完全な平方であるかどうかを確認するために使用できます。

public static boolean isPerfectSquareByUsingNewtonMethod(long n) {
    long x1 = n;
    long x2 = 1L;
    while (x1 > x2) {
        x1 = (x1 + x2) / 2L;
        x2 = n / x1;
    }
    return x1 == x2 && n % x1 == 0L;
}

3. 整数平方根アルゴリズムの最適化

すでに説明したように、整数の平方根をチェックするための複数のアルゴリズムがあります。それでも、いくつかのトリックを使用することで、いつでも任意のアルゴリズムを最適化できます。

トリックでは、平方根を決定する主な操作の実行を避けることを検討する必要があります。たとえば、負の数を直接除外できます。

私たちが使用できる事実の1つは、「完全な正方形はベース16で0、1、4、または9でしか終わらない」です。したがって、計算を開始する前に、整数を基数16に変換できます。その後、数値を不完全な平方根と見なすケースを除外します。

public static boolean isPerfectSquareWithOptimization(long n) {
    if (n < 0) {
        return false;
    }
    switch((int)(n & 0xF)) {
        case 0: case 1: case 4: case 9:
            long tst = (long)Math.sqrt(n);
            return tst*tst == n;
        default:
            return false;
    }
}