1. 개요

완전 제곱은 두 개의 동일한 정수의 곱으로 표현할 수있는 숫자입니다.

이 기사에서는 정수가 Java에서 완벽한 제곱인지 확인하는 여러 가지 방법을 알아 봅니다. 또한 효율성과 가장 빠른 방법을 결정하기 위해 각 기술의 장단점에 대해 논의 할 것입니다.

2. 정수가 완전 제곱인지 확인하기

아시다시피 Java는 정수를 정의하기 위해 두 가지 데이터 유형을 제공합니다. 첫 번째는 32 비트의 숫자를 나타내는 int 이고 다른 하나는 64 비트의 숫자를 나타내는 long 입니다. 이 기사에서는 최악의 경우 (가능한 가장 큰 정수)를 처리하기 위해 long 데이터 유형을 사용합니다 .

Java는 64 비트의 긴 숫자를 나타내므로 긴 숫자의 범위는 -9,223,372,036,854,775,808 ~ 9 , 223,372,036,854,775,807 입니다. 그리고 우리는 완전 제곱을 다루기 때문에 양의 정수 집합을 처리하는 데에만 관심이 있습니다. 정수 자체를 곱하면 항상 양수가 생성되기 때문입니다.

또한 가장 큰 수는 약 2 63 이므로 제곱이 2 63 미만인 정수 가 약 2 31.5 개 있음을 의미 합니다. 또한 이러한 숫자의 조회 테이블을 갖는 것이 비효율적이라고 가정 할 수 있습니다.

2.1. 자바 에서 sqrt 메소드 사용

정수가 완전 제곱인지 확인하는 가장 쉽고 간단한 방법은 sqrt 함수 를 사용하는 것 입니다. 아시다시피 sqrt 함수는 이중 값을 반환 합니다. 그래서 우리가해야 할 일은 결과를 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 일 수 있습니다. 따라서이 표현을 피하기 위해 0.5를 더한 후 long 으로 캐스팅 하여 실제 값을 얻습니다.

또한 하나의 숫자로 sqrt 함수를 테스트 하면 실행 시간이 빠르다는 것을 알 수 있습니다. 우리가 전화를해야하는 경우 반면에, SQRT의 기능을 여러 번, 우리가에 의해 실행 작업의 수를 줄이기 위해 노력 SQRT의 기능을 마이크로 최적화의이 종류는 실제로 차이를 만들 수 있습니다.

2.2. 이진 검색 사용

sqrt 함수 를 사용하지 않고 이진 검색을 사용하여 숫자의 제곱근을 찾을 수 있습니다 .

숫자의 범위는 1 ~ 2 63 이므로 근은 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에서 4 사이입니다. 그 이유는 한 자리의 최대 정수가 9이고 그 루트가 3이기 때문입니다. 두 자리 숫자로 구성되며 범위는 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. 정수 산술을 사용한 뉴턴의 방법

일반적으로 우리는 뉴턴의 방법을 사용하여 정수가 아닌 모든 숫자의 제곱근을 얻을 수 있습니다. 뉴턴 방법의 기본 아이디어는 숫자 X 가 숫자 N의 제곱근 이라고 가정하는 것 입니다. 그 후 루프를 시작하고 근을 계속 계산할 수 있으며, 이는 반드시 N 의 올바른 제곱근을 향해 이동할 것 입니다.

그러나 Newton의 방법을 약간 수정하면 정수가 완전한 제곱인지 여부를 확인하는 데 사용할 수 있습니다.

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. 정수 제곱근 알고리즘 최적화

논의했듯이 정수의 제곱근을 확인하는 여러 알고리즘이 있습니다. 그럼에도 불구하고 우리는 항상 몇 가지 트릭을 사용하여 모든 알고리즘을 최적화 할 수 있습니다.

트릭은 제곱근을 결정하는 주요 연산을 실행하지 않는 것을 고려해야합니다. 예를 들어 음수를 직접 제외 할 수 있습니다.

우리가 사용할 수있는 사실 중 하나는 "완벽한 제곱은 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;
    }
}

4. 결론

이 기사에서는 정수가 완전 제곱인지 아닌지를 결정하는 여러 가지 방법에 대해 논의했습니다. 우리가 본 것처럼, 우리는 항상 몇 가지 트릭을 사용하여 알고리즘을 향상시킬 수 있습니다.

이러한 트릭은 알고리즘의 주요 작업을 시작하기 전에 많은 경우를 제외합니다. 그 이유는 많은 정수가 불완전한 제곱으로 쉽게 결정될 수 있기 때문입니다.

항상 그렇듯이이 기사에 제시된 코드는 GitHub에서 사용할 수  있습니다 .